前言
很有趣的题。提供一种和现有题解略微不同的做法。
思路
突破点在于反着想。当最多能取 \(x\) 次时,每次我取的不同数字的数量,最多是多少。
统计一下每个数字出现的次数 \(cnt_i\)。那么这个最多次数应为
\[\left\lfloor\dfrac{\sum\min(cnt_i, x)}x\right\rfloor \]不妨设其为 \(T(x)\),则 \([T(x+1) + 1, T(x)]\) 的答案都是 \(x\)。
于是直接求即可。唯一的问题是如何快速求 \(T(x)\)。发现所有 \(T(i)\) 都得求出来,所以套个指针扫一遍即可,具体看代码。
线性复杂度。
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e5 + 5;
int a[N], tt[N], cnt[N];
long long tmp[N], f[N], ans[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tt[i] = a[i];
sort(a + 1, a + n + 1), sort(tt + 1, tt + n + 1);
int cur = unique(tt + 1, tt + n + 1) - tt - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(tt + 1, tt + cur + 1, a[i]) - tt;
for (int i = 1; i <= n; i++) cnt[a[i]]++;
sort(cnt + 1, cnt + cur + 1);
for (int i = 1, j = 0; i <= cur; i++)
while (j < cnt[i])
tmp[++j] = cur - i + 1;
long long sum = 0;
for (int i = 1; i <= n; i++) sum += tmp[i], f[i] = sum / i;
for (int i = 0; i <= n; i++)
for (int j = f[i + 1] + 1; j <= f[i]; j++)
ans[j] = i;
for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
return 0;
}
希望能帮助到大家!
标签:cnt,int,题解,long,ABC143F,include From: https://www.cnblogs.com/liangbowen/p/17514668.html