CF1551C Interesting Story

题意

给定 \(n\) 个仅由 \(\texttt{a,b,c,d,e}\) 组成的单词（\(n \le 2\times 10^5\)），从其中选出尽可能多的单词，使得存在某个字母在这些单词中出现的次数比其他所有字母的出现次数之和还要多。输出最多能选的单词个数。

思路

假设现在已知最终要使字母a为最后出现次数多余其他的，那么对于每一个单词，就有\(cnt\)表示该单词中a的数量比其他字母多多少（可以为负）

接着，将每个单词的\(cnt\)都求出来并从大到小排序，取前若干个，只要使选到的\(cnt\)总和为正数即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
const string letter="abcde";
struct word
{
    string s;
    int len,pre;
};
int n,maxn;
word a[Maxn];
bool cmp(word x,word y)
{
    return x.pre>y.pre;
}
int run(char c)
{
    int re=1,num=0;
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=a[i].len;j++) if(a[i].s[j-1]!=c) cnt++;
        a[i].pre=a[i].len-cnt-cnt;
    }
    sort(a+1,a+n+1,cmp);
    while(re<=n && num+a[re].pre>0) num+=a[re++].pre;
    return re-1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        maxn=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].s;
            a[i].len=a[i].s.size();
        }
        for(int i=1;i<=5;i++) maxn=max(maxn,run(letter[i-1]));
        cout<<" "<<maxn<<endl;
    }
    system("echo. & pause");
    return 0;
}