题解 CF1198A 【MP3】
wenge
2019-08-03 21:54:46
### 题目翻译：
一种保存音频的方式是保存声音在各个时刻的强度。在每个时刻，声音的强度是一个非负整数。所以我们可以把声音用包含 $n$ 个非负整数的一个数组表示。
如果在数组中恰有 $K$ 个不同值，我们需要 $k=\lceil \log_2 K\rceil$ 比特的空间存储每一个值。这需要 $nk$ 比特的空间去存储整个音频文件。
为了减少空间花费，我们需要压缩一下。一个常用的方法是减少可能的强度值的数量。我们选择两个整数 $l\leq r$，然后所有强度值将会按照如下的方式改变：如果这个强度值在区间$[l,r]$中，不对其做任何改变。如果强度值小于$l$，我们把它改成$l$；如果强度值大于$r$，我们把它改成$r$。你可以看到，很多低的强度值和高的强度值被舍弃了。
你的任务是进行这个压缩操作，使得文件能够装进一个大小为$I$字节的磁盘，并且使数组中改变的元素数量最少。
众所周知，1字节=8比特。
$k=\lceil \log_2 K\rceil$是最小的满足$K\leq 2^k$的整数。特别地，如果$K=1$，则$k=0$。
输入格式：
第一行，两个整数$n,I\ ( 1 \le n \le 4 \cdot 10^{5},1 \le I \le 10^{8})$，表示数组的长度和磁盘的空间（单位为字节）。
第二行，$n$个整数$a_i(0 \le a_{i} \le 10^{9})$，表示音频文件的数组。
输出格式：
一个整数，表示数组中改变的元素数量的最小值。
### 题解：
我们先计算出磁盘能容纳的不同值的数量。
如果磁盘的空间（单位为字节）是$I$，那么磁盘的空间（单位为比特）就是$8I$。那么$k\leq \lfloor \frac{8I}{n}\rfloor$。所以可以得到的结论是$K\leq 2^k$。所以按照上述方法把$K$的最大值算出来就可以。
但是当$I$很大的时候$K$会是一个巨大的数字。但是$n\leq400000$，所以可以给$K$设一个上限，在实际计算中也不会用到那么大的$K$值。
我们先把数组排序一下。而题目要求可以等价于在排序后的数组找一个区间，使得其包含不同元素数不超过$K$个，且长度最大，输出不在区间中的元素个数。
可以维护一个队列来记录区间。我用了简单的离散化，简化了取不同值元素个数的方法。
AC代码：
```cpp
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
//
using namespace std;
typedef long long ll;
#define clr(a,b) memset(a,b,sizeof(a));
ll n,m,x,y,ans;
int a[400005];
int b[400005];
int main(){
//ios::sync_with_stdio(false);
//cin.tie(0);
ll K=1,k;
cin>>n>>m;
m*=8;
k=m/n;
while(k--&&K<=9999999999ll)K*=2;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
b[i]=b[i-1]+(a[i]!=a[i-1]);
}
ans=0;
deque<int> q;
for(int i=1;i<=n;i++){
q.push_back(b[i]);
while(b[i]-q.front()>=K)q.pop_front();
ans=max(ans,(ll)q.size());
}
cout<<n-ans;
return 0;
}
```