题解 CF1551C 【Interesting Story】

NXYorz · 2021-07-24 09:47:20 · 题解

题目链接

题目大意

有 n 个字符串，每个字符串只包含 a,b,c,d,e 五个字符。

现在从这 n 个字符串里选择若干个，组成一个新的字符串。在满足某个字符出现的次数大于其他字符加起来出现次数的情况下，最大化新字符串的长度。

分析

以分析字符 x 为例。

对于每个字符串 i ，只需要统计出字符 x 出现的次数 cnt_1 和 其他字符出现的次数 cnt_2, 令 w_i=cnt_1-cnt_2, 这是 x 比其他字符多出现的次数，有可能为负数，最后排序一下 w， 维护一个前缀和使其大于0即可。

最后比较一下即可 qwq

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 2e5 + 10;

int t,n,ans,prt;
string s[N];

struct El
{
    int w;
    int size;
    bool operator < (const El &B) const{
        return w > B.w;
    }
}a[N];

void judge(char x)
{
    memset(a , 0 , sizeof(a)); ans = 0; 
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0; int len = s[i].length();
        for(int j = 0; j < len; j++)
            if(s[i][j] == x) cnt++;
        a[i].w = cnt - (len - cnt);a[i].size = len;
    }
    sort(a + 1 , a + 1 + n);
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        if(sum + a[i].w <= 0) break;
        sum += a[i].w; ans ++;
    }
    prt = max(prt , ans);
}

void work()
{
    scanf("%d",&n);prt = ans = 0;
    for(int i = 1; i <= n; i++)
        cin >> s[i];
    judge('a');judge('b');judge('c');judge('d');judge('e');
    printf("%d\n",prt);
}

int main()
{
//  freopen("aa.in","r",stdin);
    scanf("%d",&t);
    while(t--)
        work();

}