1 条题解
-
-5
计算存储大小时，只关心不同的强度值个数，而不关心具体的强度值是多少，因此可以用数组b记录每种强度值分别重复了多少次，其中第i小的强度值重复了b[i]次。设b数组的长度为p，然后计算b数组的前缀和，记为sum数组。计算
k = pow(2, floor(I * 8.0 / n))表示最多能存储的不同强度值个数，如果k>=p，说明不需要压缩，输出0即可。否则从左到右依次看每一个长度为k的区间，看哪种情况最优即可。核心代码
if (I * 8.0 > n * ceil(log(n) / log(2))) {//特判，存储一定够用，不需要压缩 cout << 0 << endl; return 0; } for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int cnt = 0, p = 0; for (int i = 0; i < n; i++) { if (i == 0 || a[i] == a[i - 1]) { cnt++; } else { b[p++] = cnt; cnt = 1; } } b[p++] = cnt; sum[0] = 0; for (int i = 0; i < p; i++) sum[i + 1] = sum[i] + b[i]; int k = pow(2, floor(I * 8.0 / n)); if (k >= p) { cout << 0 << endl; return 0; } int ans = sum[k]; for (int i = 1; i + k <= p; i++) ans = max(ans, sum[i + k] - sum[i]); cout << n - ans << endl;
- 1