题目传送门

思路

注意到题目给了

I

（内存），可以直接逆向求出

K

的最大值，因为我们需要最小的删除数量，显然此时

K

个不同为最优。

所以我们只需要考虑尽量删除数量更少的强度值就ok了。题目中允许

O(n)

的复杂度，删除时需要确定

l,r

删除两边，一眼双指针（区间）实现。

用桶记录相同强度的音频，可以确定中间有

K

个不同值，枚举时两边同时加，中间的和取最大值，这样删除的就最小了。

注意

$K$ 的最大值为 $n$ ，计算时特判防止过大，如果超过范围随便存。
如果强度不同数量在开始时就不及最大值，根本不需要删除，直接结束。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,x,y) for(i=x;i<=y;i++)
int a,n,k,I,ans,sum;
set<int> s;
map<int,int> m;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int i;
	cin>>n>>I;
	if(I*8/n>=31) //特判
	{
		cout<<0;
		return 0; 
	}
	k=1<<(I*8/n);//计算最大值
	F(i,1,n) //输入，计数
	{
		cin>>a;
		m[a]++;
		s.insert(a);
	}
	if(s.size()<=k) cout<<0;
	else
	{
		auto r=s.begin(),l=s.begin();
		F(i,1,k)//初始化和
		{
			sum+=m[*r];
			r++;
		}
		while(r!=s.end())//双指针枚举
		{
			sum=sum-m[*l]+m[*r];
			l++,r++;
			ans=max(ans,sum);
		}
		cout<<n-ans;//输出答案
	}
	return 0;
}

题解：CF1198A MP3

文章操作

题目传送门

思路

注意

Code

相关推荐

评论

题解：CF1198A MP3