题目链接

题目大意

给定若干个字符串,仅由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 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注