题目链接：codeforces 1199C
题目思路： 将 a [ 1 … n ] a[1…n] a[1…n] 离散化，前缀和维护区间个数。枚举区间起点，二分查找终点，取最大值。
参考代码：
#include #include #include #include #include using namespace std; typedef long long ll; const int N = 4e5 + 10; const int inf = 0x3f3f3f3f; int n, I; ll a[N], b[N], pre[N]; ll count(ll l ,ll r) { return pre[r] - pre[l-1]; } bool check(ll l, ll r) { int k = r - l + 1; return ceil(log2(k)) * n <= I * 8; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> I; for (int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; } sort(a+1, a+1+n); sort(b+1, b+1+n); ll m = unique(b+1, b+1+n) - b - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(b+1, b+1+m, a[i]) - b; for (int i = 1; i <= n; i++) { pre[a[i]]++; } for (int i = 1; i <= n; i++) { pre[i] += pre[i-1]; } ll ans = inf; for (int i = 1; i <= m; i++) { ll l = i, r = m, mid; while (l < r) { mid = (l + r + 1) >> 1; if (check(i, mid)) { l = mid; } else { r = mid - 1; } } if (check(i, l)) { ans = min(ans, n - count(i, l)); } } cout << ans << endl; return 0; }
上一篇 关于C & C++中关于字符串读入的一些小问题
下一篇 NX点亮olcd
版权所有 (c)2021-2022 MSHXW.COM
ICP备案号：晋ICP备2021003244-6号
