1198A MP3（前缀和）

阳光穿透心脏的1/2处 2021-07-16 15:08 329阅读 0赞

[题目][Link 1]

题意：给一个由n个数字组成的数组，和我们的空间大小I bytes转化为bits即为8\*I，该数组有K个不同的数字，对于每个数字我们需要用log 2 K(向上取整)bits的空间存储，现在我们有一个操作，给出一个L和R，可以使数组中小于L的元素变为L，大于R的元素变为R。问：经过了操作后，我们要使得满足存储的最小改变数字个数。

思路：我们可以给每个数字分配的空间为8*I/n，所以我们可以保有的最大不同数字个数为K0=pow(2,I*8/n（向下取整）)，然后用一个map记录各个数的数量，求一个从小到大数量前缀和。从开始遍历，每次取区间长度为K0,找出范围为K0的最大和，最后答案：为全部的不同个数-前面求到的K0最大范围值。细节见代码。

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<iomanip>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e6 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    int ls[Max];
    ll sum[Max];
    int main()
    { 
    	FAST;
    	ll n, m;cin >> n >> m;
    	map<int, int> ma;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> lst[i];ma[lst[i]]++;
    	}
    	int g = 0;ll ss = 0;
    	for (auto i = ma.begin();i != ma.end();i++)
    	{ 
    		ls[++g] = i->second;
    		sum[g] = sum[g - 1] + i->second;
    		ss += i->second;
    	}
    	m *= 8;
    	m /= n;
    	if (m >= 32)m = 2e9 + 5;
    	else m = pow(2, m);
    	ll ans = 1e9;
    	if (m >= g||g==1)cout << 0 << endl;
    	else
    	{ 
    
    		for (int i = 0;i + m <= g;i++)
    		{ 
    			ans = min(ans, ss - (sum[i + m] - sum[i]));
    		}
    		cout << ans << endl;
    	}
    }

[Link 1]: https://codeforces.ml/problemset/problem/1198/A