题解 | #艾泽拉斯大陆战争#

题目链接

艾泽拉斯大陆战争

题目描述

在艾泽拉斯大陆上，有兽族（S）、精灵族（J）和巫族（W）三个部落。当不同部落的两名成员相遇时，会发生战斗，一人死亡，另一名幸存者会转变为未参战的第三方部落的成员。

例如，一个兽族和一个精灵族战斗，幸存者会变成一个巫族。

目标是找到最少的战斗次数，使得最终大陆上只剩下一种部落的成员，实现和平。

解题思路

这道题看似是一个复杂的搜索问题，但通过分析战斗规则的数学性质，可以找到一个非常简洁的分析解法，而无需使用BFS。

1. 核心不变量：人口差的奇偶性

让我们分析一次战斗对三族人口 (s, j, w) 的影响：

S vs J: 新人口为 (s-1, j-1, w+1)
S vs W: 新人口为 (s-1, j+1, w-1)
J vs W: 新人口为 (s+1, j-1, w-1)

无论哪种战斗，每个部落的人口数都增加了或减少了1，这意味着每个部落人口的奇偶性都发生了翻转。

这个性质引出一个关键的不变量：任意两个部落之间的人口数量之差的奇偶性是恒定的。

例如，S vs J 战斗后，新的 s'-j' 差值为 (s-1) - (j-1) = s-j，差值不变。
新的 j'-w' 差值为 (j-1) - (w+1) = j-w-2，差值虽然改变，但奇偶性不变。
s'-w' 也是同理。

2. 统一的条件

大陆统一意味着最终状态是 (N', 0, 0)、(0, N', 0) 或 (0, 0, N') 中的一种。结合上面的不变量，我们可以得出结论：

要最终只剩下兽族 (N', 0, 0)，那么从始至终 (j-w) 的奇偶性必须和 (0-0) 的奇偶性相同，即初始的 (J_num - W_num) 必须是偶数。
同理，要最终只剩下精灵族，初始的 (S_num - W_num) 必须是偶数。
要最终只剩下巫族，初始的 (S_num - J_num) 必须是偶数。

3. 计算最少战斗次数

假设我们确定了可以统一成兽族（即 J_num - W_num 为偶数），现在需要计算最少战斗次数。目标是消灭所有精灵和巫族。

最有效的消灭方式就是让他们之间互相战斗。
假设有 j 个精灵和 w 个巫族，让他们一直战斗，直到一个种族被消灭。这需要 min(j, w) 场战斗。
之后，一个种族还剩下 |j-w| 人。这些人需要通过和兽族战斗来被消灭。可以证明，最终消灭这 |j-w| 人，总共还需要 |j-w| 场战斗。
所以，总战斗次数是 min(j, w) + |j-w|，这恰好等于 max(j, w)。

4. 最终算法

初始化一个最小战斗次数变量 min_fights 为无穷大。
检查是否可以统一为巫族：如果 (S_num - J_num) % 2 == 0，则更新 min_fights = min(min_fights, max(S_num, J_num))。
检查是否可以统一为精灵族：如果 (S_num - W_num) % 2 == 0，则更新 min_fights = min(min_fights, max(S_num, W_num))。
检查是否可以统一为兽族：如果 (J_num - W_num) % 2 == 0，则更新 min_fights = min(min_fights, max(J_num, W_num))。
min_fights 就是最终的答案。

这个方法避免了复杂的搜索，只需要几次简单的判断和计算。

代码

cpp
java
python

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int calc_best_fight_num(int S_num, int J_num, int W_num) {
        long long min_fights = LLONG_MAX;
        bool possible = false;

        // Case 1: W survives
        if (abs(S_num - J_num) % 2 == 0) {
            min_fights = min(min_fights, (long long)max(S_num, J_num));
            possible = true;
        }

        // Case 2: J survives
        if (abs(S_num - W_num) % 2 == 0) {
            min_fights = min(min_fights, (long long)max(S_num, W_num));
            possible = true;
        }

        // Case 3: S survives
        if (abs(J_num - W_num) % 2 == 0) {
            min_fights = min(min_fights, (long long)max(J_num, W_num));
            possible = true;
        }

        return possible ? (int)min_fights : -1; // Problem implies a solution always exists
    }
};

import java.lang.Math;

class Solution {
    public int calc_best_fight_num(int S_num, int J_num, int W_num) {
        long minFights = Long.MAX_VALUE;
        boolean possible = false;

        // Case 1: W survives
        if (Math.abs(S_num - J_num) % 2 == 0) {
            minFights = Math.min(minFights, Math.max(S_num, J_num));
            possible = true;
        }

        // Case 2: J survives
        if (Math.abs(S_num - W_num) % 2 == 0) {
            minFights = Math.min(minFights, Math.max(S_num, W_num));
            possible = true;
        }

        // Case 3: S survives
        if (Math.abs(J_num - W_num) % 2 == 0) {
            minFights = Math.min(minFights, Math.max(J_num, W_num));
            possible = true;
        }
        
        return possible ? (int)minFights : -1; // Problem implies a solution always exists
    }
}

class Solution:
    def calc_best_fight_num(self, S_num: int, J_num: int, W_num: int) -> int:
        min_fights = float('inf')
        possible = False

        # Case 1: W survives
        if abs(S_num - J_num) % 2 == 0:
            min_fights = min(min_fights, max(S_num, J_num))
            possible = True

        # Case 2: J survives
        if abs(S_num - W_num) % 2 == 0:
            min_fights = min(min_fights, max(S_num, W_num))
            possible = True

        # Case 3: S survives
        if abs(J_num - W_num) % 2 == 0:
            min_fights = min(min_fights, max(J_num, W_num))
            possible = true
        
        return min_fights if possible else -1

算法及复杂度

算法：数学分析 / 逻辑推理
时间复杂度：该算法只包含几次常数时间的算术运算和比较，因此时间复杂度为 $O(1)$ 。
空间复杂度：该算法只需要常数个变量来存储输入和结果，因此空间复杂度为 $O(1)$ 。