官方题解

T4 小午的构造

题目大意

有 a 、c 、w 三个字母若干个，有 ac 、wa 、aa 三种组合，求最多能得到多少组合，并且在得到最多组合的情况下，wa 的个数最少是多少?

解题思路

首先考虑组合出最多数量的单词：由于 c 和 w 只会被用于组成 ac 和 wa ，所有我们优先消耗 c 和 w ，最后剩下的 a 两两组合。

再来考虑如何让 wa​ 的个数尽量少：

• 在消耗 c 和 w 的情况下，我们一定优先消耗 c ，再消耗 w ；
• 当 w​ 被消耗完且 a 两两组合成 aa ，a 还有剩余时，我们可以将 wa 拆开，用其中的 a 去和剩余的 a 组合。

对于上述第二点，我们会发现最终如果有 a​ 剩余，那么一定只会剩下一个 a ，所有我们最后要拆 wa 时也只会拆一个，那么我们只需要判断组合完 ac 之后的 a 和 w 的奇偶性就可确定是否需要拆 wa 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int x,y,z;cin>>x>>y>>z;
    //先组合 ac
    int res=min(x,y);
    x=max(0ll,x-y);
    
    //如果 w 比 a 多，则将所有 a 与 w 组合
    if(x<z){
        res+=x;
        cout<<res<<" "<<x<<endl;
    }
    //否则，考虑最后是否需要拆 wa
    else{
        if((x&1)!=(z&1)) z=max(0ll,z-1);

        res+=z+(x-z)/2;
        cout<<res<<" "<<z<<endl;
    }
}

signed main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}