题意:给出序列长度n,以及空间m, 由于题意 k*n = m*8 所以 k = m*8/n; num = 2^k 即是 整个序列中不同值的个数 由于ai (1~1e9) ;然后你要把这个序列 的种类个数减小到 num 个 (问最小减小的个数)
思路:范围太大不能用 数组来记录对应个数 , 所以就使用离散化压缩一下,然后再对应统计个数,然后再找到最大的连续区间个数,这样我们减下来就是最小改变的个数0≤ai≤
完整代码:
////然后K 对应的K种 #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <queue> #define ll long long const int maxn = 4e5+1; using namespace std; int arr[maxn]; int a[maxn]; int n,m; int cont[maxn]; ll num; int main(){ while(cin>>n>>m){ int cur= 0; ll K = m*8/n; if(K>33) K=33;//注意k>32位之后我们就之间定为2^33,(太大就会超出精度) int k, Max;//k存储不同的个数,Max用于得到最大的区间和 //还有一个问题就是如果本身总类数小于num就直接输出0 for(int i=0;i<n;i++){ cin>>arr[i]; a[i] = arr[i]; } memset(cont,0,sizeof(cont)); Max = 0; num = (long long)1<<K;//num个不同的数 sort(a,a+n);//保留sort之后的状态 sort(arr,arr+n); k = unique(arr,arr+n) - arr;//不同的个数 for(int i=0;i<k;i++){ for(int j = cur;j<n;j++){ if(a[j]==arr[i]) { cont[i]++; cur++; }else{ break; } } } int tmp = 0; for(int i=0;i<n;i++){ Max = max(Max,tmp); if(i<num) tmp+= cont[i]; else{//第一组结束 tmp = tmp - cont[i-num] + cont[i]; } } if(num>=k) cout<<0<<endl; else cout<<n-Max<<endl; } }