题意：给你n个数，一个大小为8*I的容量，保存一个数需要多少容量取决于给定n个数的种类k，用公式 log2 k 计算，如果给定的容量不能保存所有数，选择减少数的种类来降低保存一个数需要的单位容量（通过替换来减少数的种类，数据的总量不变），问最少需要替换多少个数
题解：根据输入数据的关系，可以求得保存一个数需要得最小单位容量kk=8*I / n;
又因为kk= log2 k 可以解得在容量允许情况下,可以保存得最多数据种类k=2kk
又因为输入数据个数得限制n<=4*10^5; 即2kk <=4*10^5;解得kk最小等于20；
所以当kk>=20得时候，一定可以把数据完全保存----------剪枝处理
当kk<20的时候：
由kk= log2 k 解得数据种类k=2^kk (快速幂)
因为要替换的个数最少，肯定是优先替换只出现过一次的数据，
滑动窗口处理[0,k-1]:
用一个大小为k的窗口去判断在窗口内的要替换的最小个数
#include<iostream> #include<algorithm> #include<math.h> #include<string> #include<string.h> #include<vector> #include<utility> #include<map> #include<queue> #include<set> #define mx 0x3f3f3f3f #define ll long long using namespace std; map<ll,ll>m; vector<ll>p; ll a[400005]; ll quick_pow(ll base,ll k) { ll ans=1; while(k) { if(k&1) ans=ans*base; base=base*base; k=k/2; } return ans; } int main() { ll n,k,cap;//容量capacity scanf("%lld%lld",&n,&cap); for(int i=0;i<n;i++) scanf("%lld",&a[i]); sort(a,a+n); cap=cap*8;//给定的容量有多大 int kk=cap/n;//由输入的n和cap可以估计每存一个数需要的最少容量是多少 if(kk>=20)//剪枝处理，如果log以2为底kk的对数等于20，解得数字的种类k=2^20,远大于给定输入数据的个数4*10^5 { printf("0 "); return 0; } k=quick_pow(2,kk);//由估计的容量kk去解最多可以容纳几种不同的数 m[a[0]]++; p.push_back(a[0]); for(int i=1;i<n;i++) { if(a[i]!=a[i+1]) p.push_back(a[i]); m[a[i]]++; } ll cnt=p.size(); if(cnt<=k)//给定得容量能容纳这些数，就不用减少种类 { printf("0 "); return 0; } else { ll l=0,r=k-1,sum=0; for(int i=l;i<=r;i++) sum=sum+m[p[i]];//统计重复的数有几个 ll one=n-sum;//只出现一次的数的个数 l++;//滑动窗口，这个窗口的大小是k,[0,k-1] r++; while(r<cnt) { sum=sum-m[p[l-1]]+m[p[r]]; ll temp=n-sum; one=min(one,temp); l++; r++; } printf("%lld ",one); } }