Chess For Three

这是Codeforces Round 945 (Div. 2) 第一题。

题目链接

题意

三个人玩游戏，每局两个人玩。赢得人得2分，输的人得0分。平局每个人得1分。会给你三个人的最终得分，问最多平局多少局。

重点记录

这里题确实不难，但是有一个样例因为没有给怎么算的导致我一直以为样例给错了。。。

1
2
3 4 5
6

3分4分5分，最大平局数是6。

我最一开始想的是a和b平局3次，b还剩一局和c平局，这是4次。a和c平局3次，b和c平局2次，这是5次。
但是样例给的是6次。

6次的情况应该是c和a平局2次，c和b平局3次，a和b平局1次，这样就是6次。这真的是太amazing了。

题解

可以直接暴力枚举a和b，a和c，b和c平局次数，然后判断分数是否合法。除去平局的分数，剩下的分数应该left%2==0。

但是还有结论， min((p1+p2+p3)/2,p1+p2)，这里保证p1<=p2<=p3。

先考虑合不合法，三个数加一起如果是偶数就一定合法。

其次，如果p1+p2<=p3，那么情况应该是a和c平局p1次，b和c平局p2次。这就是最大的平局数。

如果p1+p2>p3，相当于p1>p3-p2。a可以和c玩p3-p2次，相当于a剩余分数为p1-(p3-p2)，这个分数一定是偶数。a还可以和b和c分别玩(p1-(p3-p2))/2次。这里a和其他人的平局数就是p1。b和c还可以平局p2-(p1-(p3-p2))/2)次。加一起就是(p1+p2+p3)/2。

标程核心：

1
cout << (v[0] + v[1] + v[2] - max(0, v[2] - v[0] - v[1])) / 2 << "\n";

暴力正解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int T;
    cin>>T;
    while(T--){
        int p1,p2,p3;
        cin>>p1>>p2>>p3;
        int ans = -1;
        // i d12,j d13,k d23
        for(int i=0;i<=30;i++){
            for(int j=0;j<=30;j++){
                for(int k=0;k<=30;k++){
                    if(p1-i-j>=0&&(p1-i-j)%2==0 &&
                       p2-i-k>=0&&(p2-i-k)%2==0 &&
                       p3-j-k>=0&&(p3-j-k)%2==0){
                        ans = max(ans,i+j+k);    
                    }
                }
            }
        }
        if(ans!=-1) cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}