挑战赛#21 T4 题解 100% AC

算法思路详解

1‌. 问题分析‌：

• 有三种单词组合方式：$ac(1a+1c)$、$aa(2a)$、$wa(1w+1a)$
• 目标：最大化单词总数，同时最小化wa单词数量
• 需要合理分配字母到不同组合方式

2. 关键策略‌：

• 枚举法‌：尝试所有可能的wa单词数量(0到z)
• 贪心分配‌：对于每种wa数量，尽可能多地组合ac，然后用剩余a组合aa
• 最优解选择‌：记录单词数最多且wa最少的方案

‌3. 变量说明‌：

• i：当前尝试的wa单词数量
• rw：剩余的w数量(未被用于wa的w)
• ra：剩余的a数量(未被用于wa的a)
• ac：能组成的ac单词数量
• aa：能组成的aa单词数量
• sum：当前方案的总单词数

4. 时间复杂度‌：

• 每组数据的时间复杂度是$O(z)$，因为需要遍历0到z的所有可能
• 总时间复杂度是$O(T*z)$，对于$T≤10^5$和$z≤100$是可接受的

5‌. 边界情况处理‌：

• 当a不足时(ra < 0)，跳过该情况
• 当所有字母都用完时，计算总单词数
• 当有多个方案单词数相同时，选择wa最少的

‌6. 为什么这个策略有效‌：

• 通过枚举所有可能的wa数量，确保不会遗漏最优解
• 对于每种wa数量，采用贪心策略最大化ac和aa数量
• 最后选择单词数最多且wa最少的方案

这个算法巧妙地结合了枚举和贪心策略，确保在合理时间内找到最优解。对于字母组合类问题，这种先枚举限制条件再贪心分配的方法很常见。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;  // 数据组数
    cin >> T;  // 输入数据组数
    
    // 处理每组数据
    while(T--) {
        int x, y, z;  // a, c, w的个数
        cin >> x >> y >> z;  // 输入字母数量
        
        int maxx = 0;  // 记录最大单词数
        int wa = 0;     // 记录wa单词的最小数量
        
        // 遍历所有可能的wa单词数量(0到z)
        for (int i = 0; i <= z; ++i) {
            int rw = z - i;  // 剩余的w数量(未被用于wa的w)
            int ra = x - i;  // 剩余的a数量(未被用于wa的a)
            
            // 如果剩余的a不够，跳过这种情况
            if (ra < 0) continue;
            
            // 计算ac单词数量：取剩余a和c的最小值
            int ac = min(ra, y);
            // 计算剩余的a(用于aa单词)
            int ra1 = ra - ac;
            // 计算aa单词数量：剩余的a可以组成ra1/2个aa
            int aa = ra1 / 2;
            // 总单词数 = wa + ac + aa
            int sum = i + ac + aa;
            
            // 更新最大单词数和最小wa数量
            if (sum > maxx) {
                maxx = sum;
                wa = i;
            } else if(sum == maxx && i < wa) {
                // 如果单词数相同但wa更少，更新wa数量
                wa = i;
            }
        }
        
        // 输出结果
        cout << maxx << " " << wa << endl;
    }
    
    return 0;
}