Moe's CF Life

哈咯，各位主人，喵~ 又到了和本喵一起学习算法的时间啦！今天我们要看的是一道关于下棋积分的有趣问题哦，Codeforces 上的 1973A - Chess For Three。别看是下棋，其实是一道可爱的数学题呢，一起来看看吧！

题目大意

有三个好朋友（就叫他们小一、小二、小三好了喵）一起玩国际象棋。

每场比赛都是两个人对战。规则是这样哒：

赢家得 2 分，输家得 0 分。
如果是平局，两个人各得 1 分。

他们玩了好多好多（也可能一局没玩）游戏之后，三个人的分数分别是 p1, p2, p3。题目保证了分数是排好序的，也就是 p1 <= p2 <= p3。

现在，需要我们计算一下，在所有可能的游戏情况中，最多可以有多少局平局呢？如果给定的分数 p1, p2, p3 根本不可能通过下棋得到，那就输出 -1。

举个栗子喵：

分数是 0 1 1：小二和小三下了一局平局，各得 1 分，小一没玩。所以最多有 1 局平局。
分数是 1 1 2：小一和小三平局一次（分数变为 1 0 1），小二和小三平局一次（分数变为 1 1 2）。总共 2 次平局。
分数是 1 1 1：这个分数是不可能达成的，所以输出 -1。

解题思路

这道题看起来有点复杂，但只要我们抓住几个关键点，问题就迎刃而解啦，喵~

关键点一：总分的奇偶性

我们先来分析一下每一局游戏对总分的影响：

一局有胜负：赢家 +2 分，输家 +0 分。总分增加 2 + 0 = 2 分。
一局是平局：两人各 +1 分。总分增加 1 + 1 = 2 分。

看到了吗？喵~ 无论是什么结果，每一局游戏都会让三个人的总分增加 2 分。这意味着，无论他们玩了多少局，最终的总分 p1 + p2 + p3 必须是一个偶数！如果总分是奇数，那肯定是搞错了，这种情况不可能发生，直接输出 -1 就好啦。

这是我们的第一个，也是最重要的判断条件！

关键点二：如何最大化平局？

我们的目标是让平局尽可能多。平局的特点是，它“温和地”给两个人各加 1 分。而胜利则“霸道地”给一个人加 2 分。为了让平局最多，我们应该优先考虑用平局来解释每个人的得分。

总共有 (p1 + p2 + p3) / 2 场游戏。如果所有游戏都是平局，那平局数自然就最大了。但这是不是总能做到呢？

这里就要分两种情况讨论了，喵~

情况一： `p1 + p2 >= p3`

这种情况，我们可以称之为“三足鼎立”的情况。分数最高的那个人的分数，也没有比另外两个人加起来还多。这就像一个稳定的三角形，每个人的分数都可以通过和另外两个人进行平局来凑齐。

我们可以证明，当 p1 + p2 >= p3 时，所有的分数都可以由平局构成。

小一和小二之间平局 (p1 + p2 - p3) / 2 次。
小一和小三之间平局 (p1 + p3 - p2) / 2 次。
小二和小三之间平局 (p2 + p3 - p1) / 2 次。

因为 p1 <= p2 <= p3，并且我们已经判断了总分是偶数，所以可以保证上面算出来的次数都是非负整数。

既然所有游戏都可以是平局，那么最多的平局数就是总游戏数啦。总游戏数 = 总分数 / 2 = (p1 + p2 + p3) / 2。

所以，在这种情况下，答案就是 (p1 + p2 + p3) / 2。

情况二： `p1 + p2 < p3`

这种情况，我们可以叫它“一家独大”。分数最高的小三，他的分数比另外两个人加起来还要多！

p1 + p2 < p3 这个条件意味着，就算小一和小二把他们所有的分数都贡献出来和小三打平局，也凑不够小三的分数。

小一最多能参与 p1 次平局（因为他总共就 p1 分，如果全是平局来的）。
小二最多能参与 p2 次平局。

为了让平局最多，我们就让小一和小二的所有分数都来自平局。他们可以和小三平局，或者他们俩互相平局。

小一和小二之间的平局，会同时消耗小一和小二的分数。
他们和小三的平局，只会消耗自己的和小三的分数。

为了让总平局数最大，我们应该让他们俩尽量和小三去平局，这样可以把小三更多的分数也解释为平局。所以，我们假设小一和小三平局了 p1 次，小二和小三平局了 p2 次。

这样，小一的分数 p1 得到了满足。
小二的分数 p2 也得到了满足。
小三通过这些平局得到了 p1 + p2 分。

总的平局数就是 p1 + p2 次。

那小三剩下的 p3 - (p1 + p2) 分怎么办呢？这些分只能通过胜利来获得了。小三必须赢下 (p3 - p1 - p2) / 2 场比赛（对手是小一或小二）。这些胜负局不影响小一和小二已经从平局中获得的 p1 和 p2 分（因为输了是得0分），所以这个构造是成立的。

在这种情况下，我们能达成的最大平局数就是 p1 + p2。

总结一下思路喵

计算总分 S = p1 + p2 + p3。
如果 S 是奇数，不可能，输出 -1。
如果 p1 + p2 >= p3，说明分数比较均衡，所有游戏都可以是平局。答案是 S / 2。
如果 p1 + p2 < p3，说明小三分数太高，平局数受限于分数较少的两人。答案是 p1 + p2。

是不是很简单呀？喵~

题解代码

下面是解题的 C++ 代码，本喵加了一些中文注释，方便主人理解哦！

cpp

#include <iostream>

// 处理单个测试用例的函数喵
void solve() {
    long long p1, p2, p3;
    std::cin >> p1 >> p2 >> p3;

    // 计算总分
    long long total_score = p1 + p2 + p3;

    // 关键点一：总分必须是偶数，因为每局游戏总分增加2
    if (total_score % 2 != 0) {
        std::cout << -1 << "\n";
        return;
    }

    // 题目保证了 p1 <= p2 <= p3，这让我们可以方便地进行比较
    
    // 关键点二，情况一：p1 + p2 >= p3
    // 这种情况说明分数分布比较均衡，可以认为所有游戏都是平局
    if (p1 + p2 >= p3) {
        // 总平局数就是总游戏数
        std::cout << total_score / 2 << "\n";
    } else {
        // 关键点二，情况二：p1 + p2 < p3
        // 这种情况说明p3的分数太高了
        // 平局的数量受限于分数较少的p1和p2
        // 最多可以构造出 p1 + p2 次平局
        std::cout << p1 + p2 << "\n";
    }
}

int main() {
    // 快速输入输出，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但背后有一些很有用的思想哦，喵~

奇偶性分析 (Parity) 这是组合数学和算法竞赛中一个非常常见的技巧。通过分析某个量在操作过程中的奇偶性变化，可以快速排除大量不可能的情况。在本题中，我们分析了总分的变化，发现它永远是偶数，从而得出了一个强力的剪枝条件。
构造性思维 (Constructive Approach) 当题目要求找到最优解（最大值/最小值）时，一个常见的思路是先推测出一个最优解的值，然后去构造一个方案来达到这个值。本题中，我们分别在 p1 + p2 >= p3 和 p1 + p2 < p3 的情况下推测出了最大平局数，并说明了如何通过安排平局和胜负局来达到这个结果，从而证明了我们的答案是正确的。
三角不等式 (Triangle Inequality)p1 + p2 >= p3 这个条件，其实就是广义上的三角不等式。在几何中，三角形两边之和大于第三边。在这里，它描述了三个玩家的分数是否“平衡”，能否构成一个完全由平局组成的“闭环”。如果满足，则可以；如果不满足，则说明有一方“过长”，无法闭合，必须通过其他方式（胜利）来弥补。

好啦，今天的题解就到这里啦！希望本喵的讲解对主人有帮助。下次再见咯，喵~

题目大意 ​

解题思路 ​

关键点一：总分的奇偶性 ​

关键点二：如何最大化平局？ ​

情况一： p1 + p2 >= p3 ​

情况二： p1 + p2 < p3 ​

总结一下思路喵 ​

题解代码 ​

知识点介绍 ​