喵哈~！各位代码大师们，你们好呀！我是你们的小助教猫娘，今天也要元气满满地和大家一起学习算法哦！这次我们要看的题目是 Codeforces 上的 1551C - Interesting Story，一个关于讲故事的问题呢，听起来就很有趣，对吧？那么，就让本猫娘带大家来分析一下吧~ ฅ'ω'ฅ

题目大意

斯蒂芬·奎恩，一位奇特的作家，他只用 'a', 'b', 'c', 'd', 'e' 这五个字母来写故事。他写下了 $n$ 个单词，现在想从这些单词里选出尽可能多的单词，组成一个“有趣的故事”。

一个故事就是一串单词的序列（可以有重复的单词哦）。那么什么样的故事算“有趣”的呢？如果故事里存在某一个字母，它在所有被选中的单词里出现的总次数，比其他所有字母出现的总次数之和还要多，那这个故事就是“有趣”的。

比如说，故事 "bac", "aaada", "e"。我们把它们拼起来看：

• 字母 'a' 出现了 1 + 3 = 4 次。
• 其他字母 ('b', 'c', 'd', 'e') 一共出现了 1 + 1 + 1 + 1 = 4 次。
• 因为 4 并不严格大于 4，所以这个例子其实在题目描述里有点小问题哦~ (´-ω-`)。一个真正有趣的例子应该是，比如 "aba" 和 "aba"。 'a' 出现了 4 次，其他字母 ('b') 出现了 2 次，4 > 2，所以这是一个有趣的故事！

我们的任务就是，从给定的 $n$ 个单词中，选出最多的单词数量，组成一个有趣的故事。如果一个单词都选不了，就输出 0。

解题思路

拿到问题，我们先来挠一挠头，分析一下这个“有趣”的条件是什么意思，喵~

一个故事是否“有趣”，取决于是否存在一个“优胜字母”。这个优胜字母的总数要严格大于所有其他字母的总数。

假设我们选了一组单词，并且我们希望字母 c 成为那个“优胜字母”。设在这些选中的单词里：

• count(c) 是字母 c 出现的总次数。
• count(others) 是所有其他字母出现的总次数。

那么“有趣”的条件就是： count(c) > count(others)

我们再想一下，所有单词的总长度 L 是不是等于 count(c) + count(others) 呢？是的呀！所以，count(others) = L - count(c)。

把这个代入上面的不等式，就得到： count(c) > L - count(c)

稍微移动一下，把 -count(c) 移到左边： 2 * count(c) > L

这个不等式是对整个故事（也就是所有被选中的单词）说的。我们可以把它分摊到每个单词上。假设我们选择的单词集合是 S： 2 * (Σ count(c, word) for word in S) > (Σ length(word) for word in S) 这里 count(c, word) 是字母 c 在单个 word 中出现的次数。

把求和符号整理一下，就变成了： Σ (2 * count(c, word) - length(word) for word in S) > 0

看！我们把复杂的条件变成了一个很清爽的数学表达式！对于每一个单词 word 和我们假定的优胜字母 c，我们可以计算一个“贡献值”：value(word, c) = 2 * count(c, word) - length(word)。我们的目标就变成了：

对于一个固定的优胜字母 c，挑选尽可能多的单词，使得这些单词的“贡献值”之和大于 0。

既然要让单词数量最多，又要让贡献值之和大于 0，一个很自然的想法就是贪心！我们应该优先选择那些“贡献值”最大的单词，因为它们对满足 > 0 这个条件最有帮助，对吧？

所以，我们的总策略就出来啦：

1. 枚举优胜字母：优胜字母只可能是 'a', 'b', 'c', 'd', 'e' 中的一个。我们就一个一个地试，总共才 5 种情况，完全没问题！
2. 计算贡献值：对于当前枚举的优胜字母（比如 'a'），我们计算出所有 $n$ 个单词的贡献值 2 * count('a', word) - length(word)。
3. 贪心选择：将这些贡献值从大到小排序。然后从最大的开始，一个一个地加起来，同时记录加了多少个单词。只要累加的和还大于 0，就说明这些单词可以组成一个有趣的故事。一旦和小于等于 0，就不能再加了，因为后面的贡献值只会更小，会让总和变得更不乐观。
4. 取最大值：对 5 个可能的优胜字母都执行一遍上面的过程，我们会得到 5 个最大单词数。我们最终的答案就是这 5 个数里的最大值！

如果自始至终都找不到能让故事变“有趣”的单词组合，那答案就是 0 啦。

代码解说

下面我们来看看这份简洁又高效的 C++ 代码是怎么实现我们的思路的，喵~

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <functional>

void solve() {
    int n;
    std::cin >> n;
    // 准备5个vector，每个对应一个字母 'a'...'e'
    // 用来存储每个单词对这个字母的“贡献值”
    std::vector<std::vector<int>> values_by_char(5);
    for (int i = 0; i < 5; ++i) {
        values_by_char[i].reserve(n); // 预分配空间，小优化~
    }

    // 遍历n个单词
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        int len = s.length();
        std::vector<int> counts(5, 0);
        // 统计当前单词s中 'a'...'e' 的数量
        for (char ch : s) {
            counts[ch - 'a']++;
        }
        // 计算并存储贡献值
        for (int j = 0; j < 5; ++j) {
            // j=0对应'a', j=1对应'b', ...
            // 计算当 j+'a' 是优胜字母时，这个单词的贡献值
            values_by_char[j].push_back(2 * counts[j] - len);
        }
    }

    int max_words = 0; // 最终答案
    // 枚举每一个可能的优胜字母
    for (int j = 0; j < 5; ++j) {
        // 把该字母对应的所有贡献值从大到小排序
        std::sort(values_by_char[j].begin(), values_by_char[j].end(), std::greater<int>());
        
        long long current_sum = 0;
        int current_count = 0;
        // 贪心选择
        for (int val : values_by_char[j]) {
            current_sum += val;
            if (current_sum > 0) {
                // 如果总和大于0，说明这组单词是“有趣”的
                current_count++;
            } else {
                // 否则，不能再加了，后面的只会更差
                break;
            }
        }
        // 更新全局最大单词数
        if (current_count > max_words) {
            max_words = current_count;
        }
    }
    std::cout << max_words << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码的逻辑和我们刚才梳理的思路一模一样，非常清晰~

• values_by_char 这个二维向量设计得很巧妙，values_by_char[j] 存的就是当 j+'a' 作为优胜字母时，所有单词的贡献值列表。
• 外层循环 for (int j = 0; j < 5; ++j) 实现了对优胜字母的枚举。
• std::sort 和 std::greater<int>() 漂亮地完成了从大到小排序。
• 内层的 for (int val : ...) 循环则执行了贪心策略，累加贡献值并更新计数。
• 最后，max_words 记录了所有情况下的最优解。

知识点介绍

这道题虽然是 C 题，但用到的思想可是非常重要和基础的哦！

1. 贪心算法 (Greedy Algorithm) 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。这道题里，我们每次都选“贡献值”最大的单词，就是典型的贪心思想。贪心算法不一定总能得到全局最优解，但在这道题的特定问题模型下，它是正确的！

2. 问题转换 (Problem Transformation) 这是解决算法题的一个核心技巧！我们把一个看起来有点模糊的文字描述（“一个字母比所有其他字母加起来都多”），通过一步步的数学推导，转换成了一个清晰的代数不等式 Σ(2 * count - len) > 0。这个转换是解题的关键，它让问题变得可以用贪心等标准算法来解决。

3. 枚举 (Enumeration) 当问题中某个变量的取值范围很小的时候，我们就可以“偷懒”啦，直接把它所有可能的情况都试一遍。在这里，优胜字母只有 5 种可能，所以我们完全可以为每一种情况都计算一次最优解，然后取最好的那个。这是一种简单粗暴但非常有效的方法，喵~

好啦，今天的题目讲解就到这里啦！希望本猫娘的解释能帮到大家。只要把问题分析透彻，找到正确的切入点，再复杂的题目也会变得像毛线球一样好玩哦！下次再见，喵~ (ฅ^•ﻌ•^ฅ)