Tối đa hóa số chỉ số thỏa mãn a[i+1] > a[i] bằng cách sắp xếp lại mảng trong C++

Đề bài

Cho mảng N số nguyên. Sắp xếp lại để tối đa hóa số chỉ số i thỏa mãn arr[i+1] > arr[i].

Ví dụ: {300,400,400,300} → sắp xếp {300,400,300,400} → 2 chỉ số thỏa mãn.

Thuật toán

• Nếu tất cả phần tử khác nhau → kết quả = n-1 (sắp xếp tăng dần).
• Nếu có phần tử trùng lặp → kết quả = n - maxFrequency (tần suất lớn nhất của bất kỳ giá trị nào).

Lý do: Phần tử xuất hiện nhiều nhất tạo ra các "khoảng trống" buộc phải đặt các giá trị khác vào giữa, mỗi lần lặp lại giảm 1 cặp tăng.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
#define MAX 1000
using namespace std;

int getMaxIndices(int* arr, int n) {
    int count[MAX] = {0};
    for (int i = 0; i < n; ++i) count[arr[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        maxFreq = max(maxFreq, count[arr[i]]);
    return n - maxFreq;
}

int main() {
    int arr[] = {300, 400, 300, 400};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Ket qua = " << getMaxIndices(arr, n) << endl;
    return 0;
}

Kết quả

Ket qua = 2