题解 | #破壁#_牛客博客

题目链接

破壁

题目描述

Alice 和 Bob 进行一个回合制游戏。有 $n$ 扇门，第 $i$ 扇门的初始耐久度为 $h_i$ 。

在 Alice 的回合，她选择一扇门，将其耐久度减少 $x$ 。当一扇门的耐久度小于等于 $0$ 时，门被破开。

在 Bob 的回合，他选择一扇未被破开的门，将其耐久度增加 $y$ 。

Alice 的目标是最大化被破开的门的数量，而 Bob 的目标是最小化。在双方都采取最优策略的情况下，求最后被破开的门的数量。

预估难度

CodeForces: 1500
知识点: 博弈论、贪心
难度评估: 本题的核心在于分析双方在不同情况下的最优策略。当 Alice 的攻击力 $x$ 大于 Bob 的修复能力 $y$ 时，局面相对简单；而当 $x \le y$ 时，问题转化为一个在特定子集上的轮流选择问题。这个转化需要一定的博弈论思维，但不涉及复杂算法，因此综合评定为 1500。

解题思路

这是一个典型的博弈论问题，双方的决策都围绕着最大化或最小化最终收益（破开的门数）。最优策略的分析需要根据 Alice 的攻击力 $x$ 和 Bob 的修复能力 $y$ 的关系进行分类讨论。

情况一： $x > y$

当 Alice 的攻击力大于 Bob 的修复能力时，Alice 占据绝对优势。

最优策略分析: 无论 Bob 如何选择修复，只要 Alice 持续攻击同一扇门，该门的耐久度在每个完整回合（Alice 攻击 + Bob 修复）后，净减少值为 $x-y > 0$ 。因此，只要 Alice 坚持，任何一扇门都终将被破开。
Bob 的对策: Bob 最优的策略是修复 Alice 正在攻击的门，以最大限度地拖延时间，但无法从根本上阻止门的破坏。如果 Bob 修复其他门，只会让 Alice 更快地破开当前目标。
结论: 既然 Alice 可以逐个破开所有的门，并且游戏会持续到无法破开新门为止，那么在这种情况下，所有 $n$ 扇门最终都会被破开。

情况二： $x \le y$

当 Alice 的攻击力不大于 Bob 的修复能力时，Bob 有能力阻止 Alice 对一扇门造成持续伤害。

最优策略分析: 如果 Alice 攻击一扇门，而 Bob 立即修复它，那么这扇门的耐久度在经历一个完整回合后不会减少（甚至会增加）。这意味着，Alice 无法通过“磨血”的方式破开一扇有 Bob 防守的门。
Alice 的机会: Alice 唯一能破开门的机会，是在 Bob 来不及修复之前，通过一次攻击就将门的耐久度降至 $0$ 或以下。这只对初始耐久度 $h_i \le x$ 的门有效。
博弈转化: 于是，问题转化为一个只在这些初始耐久度 $h_i \le x$ 的门之间进行的博弈。我们称这些门为“脆弱门”。设共有 $k$ 扇脆弱门。
- Alice 的最优策略: 在她的回合，选择一扇当前最脆弱（即耐久度最低）的门进行攻击，确保将其破开。
- Bob 的最优策略: 在他的回合，为了阻止 Alice 在未来破开更多的门，他必须选择一扇还未被破开的脆弱门进行修复，使其耐久度增加到 $x$ 以上，从而摆脱“脆弱”状态。
轮流选择: 这个过程变成了一个轮流选择的游戏：
1. Alice 先手，从 $k$ 扇脆弱门中选择一扇并“移除”（破开）。
2. Bob 后手，从剩下的脆弱门中选择一扇并“移除”（修复）。
3. 双方轮流进行，直到所有脆弱门都被处理。
结论: 由于 Alice 先手，她将进行第 1、3、5、... 次选择，而 Bob 进行第 2、4、6、... 次选择。在总共 $k$ 次选择中，Alice 能成功破开的门数是她行动的次数，即 $\lceil \frac{k}{2} \rceil$ 。这在整数除法中等价于 $(k+1)/2$ 。

算法总结

比较 $x$ 和 $y$ 。
如果 $x > y$ ，结果为 $n$ 。
如果 $x \le y$ ，则统计初始耐久度 $h_i \le x$ 的门的数量，记为 $k$ 。结果为 $(k+1)/2$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    long long x, y;
    cin >> n >> x >> y;
    vector<long long> h(n);
    int vulnerable_count = 0;
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
        if (h[i] <= x) {
            vulnerable_count++;
        }
    }

    if (x > y) {
        cout << n << endl;
    } else {
        cout << (vulnerable_count + 1) / 2 << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long x = sc.nextLong();
        long y = sc.nextLong();
        
        int vulnerable_count = 0;
        for (int i = 0; i < n; i++) {
            long h = sc.nextLong();
            if (h <= x) {
                vulnerable_count++;
            }
        }
        
        if (x > y) {
            System.out.println(n);
        } else {
            System.out.println((vulnerable_count + 1) / 2);
        }
    }
}

import sys

def main():
    n, x, y = map(int, sys.stdin.readline().split())
    h = list(map(int, sys.stdin.readline().split()))
    
    if x > y:
        print(n)
    else:
        vulnerable_count = 0
        for health in h:
            if health <= x:
                vulnerable_count += 1
        print((vulnerable_count + 1) // 2)

if __name__ == "__main__":
    main()

算法及复杂度

算法: 博弈论、贪心、分类讨论
时间复杂度: $\mathcal{O}(n)$ ，其中 $n$ 是门的数量。主要开销在于读取和遍历一次所有门的耐久度。
空间复杂度: $\mathcal{O}(n)$ ，用于存储 $n$ 扇门的初始耐久度。如果输入可以流式处理，则可以优化到 $\mathcal{O}(1)$ 。