Tích lớn nhất từ mảng với điều kiện tần suất phần tử lặp ≤ 2*k trong C++

Cho mảng và số k. Tìm tích lớn nhất của một tập con sao cho tổng (tần suất - 1) của các phần tử lặp trong tập con ≤ 2*k.

Thuật toán

• Sắp xếp mảng.
• Đếm tần suất mỗi giá trị.
• Nhân tất cả giá trị khác nhau một lần vào tích.
• Từ giá trị lớn nhất, thêm các bản sao thừa (tần suất-1) cho đến khi hết k.

Ví dụ triển khai (C++)

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

ll maxProd(int arr[], int n, int k) {
    ll product = 1;
    unordered_map<int, int> freq;
    sort(arr, arr + n);
    for (int i = 0; i < n; i++) {
        if (freq[arr[i]] == 0) product *= arr[i];
        freq[arr[i]]++;
    }
    for (int j = n-1; j >= 0 && k > 0; j--) {
        int extra = freq[arr[j]] - 1;
        if (extra > 0) {
            int take = min(k, extra);
            product *= pow(arr[j], take);
            k -= take;
            freq[arr[j]] = 0;
        }
    }
    return product;
}

int main() {
    int arr[] = {5, 6, 7, 8, 2, 5, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << maxProd(arr, n, k);
    return 0;
}

Đầu ra

161280