https://codeforc.es/contest/1199/problem/C
擦,最后移位运算符溢出了,真的蠢。
肯定是选中间的连续的某段是最优的,维护这个段的长度和其中的元素种类就可以了。小心x可能很大导致溢出。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read() {
int x = 0;
int f = 0;
char c;
do {
c = getchar();
if(c == '-')
f = 1;
} while(c < '0' || c > '9');
do {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
} while(c >= '0' && c <= '9');
return f ? -x : x;
}
inline void _write(int x) {
if(x > 9)
_write(x / 10);
putchar(x % 10 + '0');
}
inline void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
_write(x);
putchar('\n');
}
int n, I, x, len;
int a[400005];
map<int, int> m;
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
n = read(), I = read();
x = (8 * I) / n;
if(x >= 30)
x = 30;
len = (1 << x);
for(int i = 1; i <= n; ++i)
a[i] = read();
sort(a + 1, a + 1 + n);
int l = 1, r = 1;
m[a[1]]++;
int cnt1 = 1, cnt2 = 1, ans = n - 1;
while(r < n) {
r++;
int t = m[a[r]]++;
cnt2++;
if(t == 0)
cnt1++;
while(cnt1 > len) {
int tmp = m[a[l]]--;
if(tmp == 1)
cnt1--;
l++;
cnt2--;
}
ans = min(ans, n - cnt2);
}
printf("%d\n", ans);
}