题目大意
给定若干个字符串,仅由a,b,c,d,e五种字母构成,尽可能多的选择其中的字符串,使其选中的字符串中有一种字母占比高出50%
解题思路
对于五种字母,都去实验一遍;
要求是让某种字符的数量比其它字符多
那对于每个字符串,我们求出该字符的数量与其它字符数量的差
然后贪心,尽可能取差值较大的字符串,且总和要大于零
取的数的数量就是取的字符串的数量
代码实现
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+7;
const int eps = 1e-8;
const int inf = 0x7f7f7f7f;
const int mod = 1e9+7;
int T;
int n,m,k;
struct node{
int a,b,c,d,e;
int len;
}z[N];
string s[N];
int A,B,C,D,E,LEN,hh;
int cmpA(node q,node w){
int fa=2*q.a-q.len;
int fb=2*w.a-w.len;
return fa>fb;
}
int cmpB(node q,node w){
int fa=2*q.b-q.len;
int fb=2*w.b-w.len;
return fa>fb;
}
int cmpC(node q,node w){
int fa=2*q.c-q.len;
int fb=2*w.c-w.len;
return fa>fb;
}
int cmpD(node q,node w){
int fa=2*q.d-q.len;
int fb=2*w.d-w.len;
return fa>fb;
}
int cmpE(node q,node w){
int fa=2*q.e-q.len;
int fb=2*w.e-w.len;
return fa>fb;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int T = 1;
cin>>T;
int ans=0;
while(T--){
ans=0;
cin>>n;
for(int i=1;i<=n;i++){
s[i].clear();
z[i].a=z[i].b=z[i].c=z[i].d=z[i].e=z[i].len=0;
}
for(int i=1;i<=n;i++){
cin>>s[i];
m=s[i].length();
for(int j=0;j<m;j++){
if(s[i][j]=='a') z[i].a++;
if(s[i][j]=='b') z[i].b++;
if(s[i][j]=='c') z[i].c++;
if(s[i][j]=='d') z[i].d++;
if(s[i][j]=='e') z[i].e++;
}
z[i].len=s[i].length();
}
sort(z+1,z+n+1,cmpA);
A=B=C=D=E=LEN=hh=0;
for(int i=1;i<=n;i++){
A+=z[i].a;
B+=z[i].b;
C+=z[i].c;
D+=z[i].d;
E+=z[i].e;
LEN+=z[i].len;
if(2*A>LEN){
if(B*2!=LEN && C*2!=LEN && D*2!=LEN && E*2!=LEN){
ans=max(ans,i);
}
}
else{
break;
}
}
sort(z+1,z+n+1,cmpB);
A=B=C=D=E=LEN=hh=0;
for(int i=1;i<=n;i++){
A+=z[i].a;
B+=z[i].b;
C+=z[i].c;
D+=z[i].d;
E+=z[i].e;
LEN+=z[i].len;
if(2*B>LEN){
if(A*2!=LEN && C*2!=LEN && D*2!=LEN && E*2!=LEN){
ans=max(ans,i);
}
}
else{
break;
}
}
sort(z+1,z+n+1,cmpC);
A=B=C=D=E=LEN=hh=0;
for(int i=1;i<=n;i++){
A+=z[i].a;
B+=z[i].b;
C+=z[i].c;
D+=z[i].d;
E+=z[i].e;
LEN+=z[i].len;
if(2*C>LEN){
if(B*2!=LEN && A*2!=LEN && D*2!=LEN && E*2!=LEN){
ans=max(ans,i);
}
}
else{
break;
}
}
sort(z+1,z+n+1,cmpD);
A=B=C=D=E=LEN=hh=0;
for(int i=1;i<=n;i++){
A+=z[i].a;
B+=z[i].b;
C+=z[i].c;
D+=z[i].d;
E+=z[i].e;
LEN+=z[i].len;
if(2*D>LEN){
if(B*2!=LEN && C*2!=LEN && A*2!=LEN && E*2!=LEN){
ans=max(ans,i);
}
}
else{
break;
}
}
sort(z+1,z+n+1,cmpE);
A=B=C=D=E=LEN=hh=0;
for(int i=1;i<=n;i++){
A+=z[i].a;
B+=z[i].b;
C+=z[i].c;
D+=z[i].d;
E+=z[i].e;
LEN+=z[i].len;
if(2*E>LEN){
if(B*2!=LEN && C*2!=LEN && D*2!=LEN && A*2!=LEN){
ans=max(ans,i);
}
}
else{
break;
}
}
cout<<ans<<endl;
}
return 0;
}
0 条评论