题目链接：Codeforces 1199C
统计每个数字出现的个数，考虑贪心地去最大的 \(K\)，删掉最少的数。对于 \(k = \lceil \log_2 K \rceil\) 固定的时候，取 $k = _2 K $ 即 \(K = 2 ^ k\) 最大。而从 \(n k \leq 8I\) 可以看出 \(k_{\max} = \lfloor \frac{8I}{n} \rfloor\)，因此我们可以求出最多可以保留多少种数（注意 \(K\) 小于等于种类总数）和最少删掉多少种数，枚举前面删几个后面删几个即可，预处理前缀和。
坑点：1<<k会爆int，应当使用1LL<<k。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 400000 + 5;
LL n, I, a[MAX_N];
LL num[MAX_N], tot;
LL pre[MAX_N], suf[MAX_N];
map <LL, LL> h;
int main() {
scanf("%lld%lld", &n, &I);
for (int i = 1; i <= n; ++i) scanf("%lld", a + i), ++h[a[i]];
for (auto const &e: h) num[++tot] = e.second;
LL k = 8 * I / n, K;
K = (k > 31 ? INT_MAX : (1LL << k));
K = min(K, tot);
for (int i = 1; i <= tot; ++i) pre[i] = pre[i - 1] + num[i];
for (int i = tot; i >= 1; --i) suf[i] = suf[i + 1] + num[i];
LL del = tot - K;
LL ans = INT_MAX;
for (int i = 0; i <= del; ++i) {
ans = min(ans, pre[i] + suf[tot - (del - i) + 1]);
}
printf("%lld\n", ans);
return 0;
}
|