题解：CF1198A MP3

weisongze · 2025-01-15 16:27:55 · 题解

题目传送门

思路

注意到题目给了 I（内存），可以直接逆向求出 K 的最大值，因为我们需要最小的删除数量，显然此时 K 个不同为最优。

所以我们只需要考虑尽量删除数量更少的强度值就ok了。题目中允许 O(n) 的复杂度，删除时需要确定 l,r 删除两边，一眼双指针（区间）实现。

用桶记录相同强度的音频，可以确定中间有 K 个不同值，枚举时两边同时加，中间的和取最大值，这样删除的就最小了。

注意

如果强度不同数量在开始时就不及最大值，根本不需要删除，直接结束。
Code

#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