Chess For Three
Chess For Three
这是Codeforces Round 945 (Div. 2) 第一题。
题意
三个人玩游戏,每局两个人玩。赢得人得2分,输的人得0分。平局每个人得1分。会给你三个人的最终得分,问最多平局多少局。
重点记录
这里题确实不难,但是有一个样例因为没有给怎么算的导致我一直以为样例给错了。。。
1 | 3 4 5 |
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 |
|
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment