Thematic Contests

Created by LXC on Thu Jul 20 00:03:04 2023

https://codeforces.com/problemset/problem/1077/E

ranting: 1800

tag: greedy, sortings

problem

现在在举行若干场编程竞赛，可选的题目有n个，每个题都有一个主题。

一场比赛的题目都属于同一个主题。

一场比赛的题目不限。

如果举行了多场比赛，后一场比赛的题目数目必须是前一场的2倍。

现在对比赛场数不限制，求最多能选多少个题目。

solution

预处理cnt[i]代表题目个数为i个的主题的个数。

求其后缀和，得到cnt[i]代表题目个数至少为i个的主题的个数。

枚举初始比赛的题目个数x，由于一场比赛的题目属于同一个主题，所以枚举的上界不超过mx，mx为拥有题目最多的主题的题数。显然mx不超过n。

后续的比赛是前一场的两倍，我们只需要检测cnt[x] cnt[2x] cnt[4x] ... 都非0，则答案就是x+2x+4x+...。

值得注意的是，当我们遇到cnt[kx] = 1时，此时只有1个主题的题数为kx，因此需要停止后续的检测。另外由于题目个数大于x的主题个数为cnt[x]，当所有检测的个数不超过cnt[x]个。

对于每个枚举的x，内层检测的枚举下标是x乘以2的幂次，内层复杂度是$log(n/x)$。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    // for (int i : a) {
    //     cout << i << " ";
    // }
    // cout << endl;
    vector<int> cnt(n + 1);
    int mx = 0;
    for (int i = 0; i < n;) {
        int p = i;
        while (p < n && a[p] == a[i])
            p++;
        mx = max(mx, p - i);
        cnt[p - i]++;
        i = p;
    }
    for (int i = mx - 1; i >= 0; i--) {
        cnt[i] += cnt[i + 1];
    }
    ll ans = 0;
    for (ll i = 1; i <= mx; i++) {
        ll c = 0;
        for (int j = i, k = cnt[j]; j <= mx && k; j *= 2, k--) {
            c += j;
            if (cnt[j] == 1)
                break;
        }
        ans = max(ans, c);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}