CF1198

Codeforces Round 576 (Div. 1)

CF1198A

link

CF1198A题意

有一种数字化一段录音的常用方式，是记录每一个时刻的强度值。这些非负的强度值就可以代表一段音频

对于一段音频，若有 \(K\) 个不同的强度值，那么每一位我们都需要 \(k = \lceil\log_2K \rceil\) \(\text{bit}\) 来存储

也就是说，为了存储这一段音频，我们需要 \(nk\) 个 \(\text{bit}\)

为了压缩音频大小，我们们采取如下的方式：

选择两个整数 \(l, r(l \leq r)\)，对于音频的强度值序列 \(v\)，将其作一次变换：

\[v_i = \begin{cases} v_i&l \leq v_i \leq r \\ l &v_i < l\\ r &r < v_i \end{cases} \]

其中第 \(2, 3\) 种情况被视作 \(v_i\) 这个强度值被更改了

你的任务是对于给定的强度值序列 \(a\)，找到一组 \(l, r\)，使得在经过上述压缩后能够被大小为 \(I \ \text{bytes} (\text{1bytes = 8 bit})\) 的存储器装下，并最小化被更改的强度值的数量。

CF1198A题解

~~坏了坏了，Eric被1600爆杀了（~~
首先别读错题，\([l,r]\) 表示值域范围，不是下标范围。
然后计算最多保留的不同数字 \(k = 2^{\lfloor\frac{I}{n}\rfloor}\)。
直接暴力枚举左端点 \(l=i\)，则 \(r=i+k-1\)，预处理下在这个范围之外的数字有多少个即可。
时间复杂度 \(O(n)\)

CF1198A代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 4e5 + 10;
int n, I;
int a[maxn], b[maxn];
int pre[maxn], suf[maxn];
int buc[maxn];
int qpow(int x,int a){
    int res = 1;
    while(a){
        if(a & 1)res = res * x;
        if(res >= n)return n;
        x = x  * x;a >>= 1;
        if(x >= n)x = n;
    }
    return res;
}
signed main(){
    n = read(); I = read() * 8;
    for(int i = 1;i <= n;i++){b[i] = a[i] = read();}
    sort(b + 1,b + 1 + n);
    int tot = unique(b + 1,b + 1 + n) - b - 1;
    for(int i = 1;i <= n;i++){a[i] = lower_bound(b + 1,b + 1 + tot,a[i]) - b;}
    for(int i = 1;i <= n;i++)buc[a[i]]++;
    for(int i = 1;i <= tot;i++)pre[i] = buc[i] + pre[i - 1];
    for(int i = tot;i;i--)suf[i] = buc[i] + suf[i + 1];
    int ans = n, k = qpow(2,I / n);
    if(k >= tot){puts("0");return 0;}
    for(int i = 1;i + k - 1 <= tot;i++) ans = min(ans,pre[i - 1] + suf[i + k]);
    printf("%lld\n",ans);

    // printf("tot = %lld, k = %lld\n",tot, k);
    return 0;
}