CF1551B1 题解

原题链接：https://www.luogu.com.cn/problem/CF1551B1

题目大意

1. 给定一个字符串，每个字母可以染成红色和蓝色或者不染色。
2. 保证红色和蓝色的字母数量一样多。
3. 同样的字母不能染成同样颜色。
4. 使染色数量尽可能多。

题目分析

依题意每个字母有 $3$ 种情况：红色、蓝色、不染色，而根据上面的第 $3$ 条原则，我们可以看出来如果一个字母出现了第 $3$ 次及以上，那么第 $3$ 次及以后的该字母不能被染色，因此我们可以建一个数组来记录某个字符的出现次数，进而统计出能被染色的字母数目。
进一步分析，假定有 55 个字母可以被染色，那么能染色的最大数量为 $4$ ，即染红色数量为 $2$ 。假定有 $4$ 个字母可以被染色，那么能染色的最大数量为 $4$ ，即染红色数量为 $2$ 。同理推知，用 $N$ 表示能染色的数目，最终被染成红色的最大数目为 $N \div 2$.

核心代码

int main() {
    int n;
    scanf("%d",&n);
    while(n--){
        string str;
        int a[26]={0};//统计26个字母的个数
        cin>>str;   
        int cnt=str.size();//设cnt为能被染色的字母大小
        int tmp=cnt;//用tmp存储字符串大小
        for(int i=0;i<tmp;i++){//计算能被染色的字母个数
            a[str[i]-'a']++;//该字母出现次数加1
            if(a[str[i]-'a']>=3){
                cnt--;//如果该字母重复3次及以上 则该字母的第三次及以后重复都无法被染色
            }
        }//算出来能被染色的字母个数
        cout<<cnt/2<<endl;
        }
    return 0;
}