非官方题解|挑战赛#21-T4

T4小午的构造

• 难度：普及-

• 思路分析

1. 优先构造ac单词：
   首先计算能构造的ac单词数量 $c$ ，取 $x$ 和 $y$ 的最小值
   这样能同时消耗 $a$ 和 $c$ ，保证不浪费 $c$ 字母（$c$字母仅能构造ac）
2. 处理剩余字母：
   计算构造ac后剩余的 $a$ 数量 $r=x-c$
   计算能构造的 wa 数量 $w$ ，取 $z$ 和 $r$ 的最小值
   调整 $w$ 使得剩余的 $a$ 能两两组合成 aa
wa尽可能的少
3. 构造aa单词：
   剩余 $a$ 数量为 $r-w$ ，计算能构造的aa数量$a=(r-w)/2$
   确保所有字母被用完且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;
        
        //构造所有可能的ac单词 
        int c=min(x,y);//ac数量取a和c的较小值 
        int r=x-c;    //构造ac后剩余的a数量
        
        //计算可能的wa数量 
        int w=min(z,r);//wa数量取w和剩余a的较小值
        //调整w使剩余a能两两组合
        w=max(w-(r-w)%2,0);//确保(r-w)是偶数 
        
        //计算aa数量
        int a=(r-w)/2; // 剩余a构造的aa数量 

        cout<<c+a+w<<' '<<w<<endl;
    } 
}

• 时间复杂度分析：

仅有处理 $t$ 组测试用例是涉及循环，时间复杂度 $O(t)$。