题意
给定 \(n\) 个只含 \(a\) 到 \(e\) 的字符串,求最多能选出多少个字符串,使得存在某个字母出现次数严格大于其它字母。
分析
首先我们看下数据范围,2e5的然后\(a-e\)只有5个字符,所以我们可以贪心的想,就是把符合的提取出来就行了,严格大于其他字符是说,某一字符数量大于其他字符数量和。
然后我们看,同一个串中某一字符比其他字符多多少,字符长度为len,当前字符长度为x那么当前字符比其他字符多\(x*2-len\),就是其他字符数量为\(len-x\),\(x-(len-x)\).
之后排序贪心选代价大于0求出最多能选多少个。
void solve(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
for(int j=0;j<5;j++){
num[i][j]=0;
}
}
for(int i=1;i<=n;i++){
cin>>str;
for(int j=0;j<(int)str.size();j++){
++num[i][str[j]-'a'];
}
for(int j=0;j<5;j++){///jiazhi
ans[j][i]=2*num[i][j]-str.size();
}
}
ll res=0;
for(int i=0;i<5;i++){
sort(ans[i]+1,ans[i]+n+1);
ll a,b;
a=b=0;
for(int j=n;j>0;j--){
if(b+ans[i][j]>0) {
b+=ans[i][j];
++a;
}
res=max(res,a);
}
}
printf("%lld\n",res);
}