[数据结构与算法][贪心+排序]CF101A题解

题目传送门

思路

总的来说这个题目就是 贪心 $+$ 排序。题目意思比较明确，这里将不再阐述。

首先，他要让我们在删去 $k$ 个字符之后，留下的字母种类数尽量的小，也就是让删去的种类尽量的多。我们可以运用桶的思想，将每个字母的数量储存下来，为了让删去的种类越多，我们先根据这个字母的数量从小到大排序，然后每次都先删去数量越少的字母。因为这样的话，我们可以删去的 $k$ 个字符才能利用到最大化，使得他能删去更多的字母种类。

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char a[100005];
int n,m;
struct node
{
    int p,id;//p储存数量，id储存这个字母。
    bool operator <(const node &n)const
    {
        return p<n.p;//根据数量进行排序。
    }
}arr[100005];
int vis[100005],cnt;//vis标记每个字母在结构体中的下标
int ans;
int main()
{
    cin>>a+1;
    n=strlen(a+1);
    cin>>m;
    for(int i=1;i<=n;++i)
    {
    	//运用桶的思想储存。
        if(vis[a[i]]==0)
        ans++,vis[a[i]]=++cnt;//记得将答案默认为当前的字母种类。
        arr[vis[a[i]]].p++;
        arr[vis[a[i]]].id=a[i];
    }
    sort(arr+1,arr+cnt+1);//排序。
    for(int i=1;i<=cnt;++i)
    {
    	//判断是否可以继续删除一个字母种类
        m-=arr[i].p;
        if(m>=0)
        ans--,arr[i].p=0;//被删除了，将数量标记为0，答案-1
        else if(m<0)
        {
            break;//不能被删除就直接跳出循环。
        }
    }
    cout<<ans<<endl;//输出种类
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i)
    {
        int q;
        for(int j=1;j<=cnt;++j)
        {
            if(arr[j].id==a[i])
            {
                q=arr[j].p;//找到a_i这个字母是否被删除
                break;
            }
        }
        for(int j=1;j<=min(1,q);++j)//如果这个字母没有被删除就输出，被删除了q就是0，就不会输出。
        cout<<a[i];
    }
    cout<<endl;
}