Số phần tử tối đa có thể làm bằng nhau với k lần cập nhật trong C++

Phương pháp

• Sắp xếp mảng tăng dần.
• Tính mảng tiền tố p[] và mảng max m[].
• Tìm kiếm nhị phân đáp án: với độ dài x, kiểm tra có thể làm x phần tử bằng nhau không.
• Kiểm tra: với cửa sổ kích thước x, chi phí = x * m[j] - (p[j] - p[i]) ≤ k.

Ví dụ

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

bool EleCal(int p[], int m[], int x, int k, int size) {
    for (int i = 0, j = x; j <= size; j++, i++) {
        if (x * m[j] - (p[j] - p[i]) <= k)
            return true;
    }
    return false;
}

void Max(int arr[], int size, int k) {
    sort(arr, arr + size);
    int p[size + 1];
    int m[size + 1];
    for (int i = 0; i <= size; ++i) {
        p[i] = 0;
        m[i] = 0;
    }
    m[0] = arr[0];
    p[0] = arr[0];
    for (int i = 1; i < size; i++) {
        p[i] = p[i - 1] + arr[i];
        m[i] = max(m[i - 1], arr[i]);
    }
    int Lt = 1, Rt = size, result;
    while (Lt < Rt) {
        int mid = (Lt + Rt) / 2;
        if (EleCal(p, m, mid - 1, k, size)) {
            result = mid;
            Lt = mid + 1;
        } else
            Rt = mid - 1;
    }
    cout << result;
}

int main() {
    int a[] = { 1, 3, 8 };
    int size = sizeof(a) / sizeof(a[0]);
    int k = 4;
    Max(a, size, k);
    return 0;
}

Đầu ra

2