[NCT058C2]简单题 - 题解

标签与难度

标签: 二分答案, 贪心, 排序, 线性函数, 游戏策略, 整数溢出难度: 1800

题目大意喵~

Nyahello~！各位指挥官，小 C 的战争游戏开始了哦！

我们一开始有 $n$ 个堡垒，目标是占领另外 $n$ 个敌人的堡垒。总共有 $2n$ 个堡垒。每个堡垒 $i$ 的战斗力 $w_i$ 都会随着时间 $t$ 变化，关系是 $w_i(t) = k_i \cdot t + b_i$ ，其中 $k_i$ 是战斗力变化率， $b_i$ 是初始战斗力。

在任意一个整数时刻 $t$ ，我们的堡垒 $i$ 可以打败敌人堡垒 $j$ 的条件是 $w_i(t) \ge w_j(t)$ 。一旦获胜，我们的驻军就会从堡垒 $i$ 转移到堡垒 $j$ ，也就是说，我们失去了堡垒 $i$ ，但获得了堡垒 $j$ 。这就像是一次一对一的交换，我们手里的堡垒总数还是 $n$ 个。

我们的任务是，找到一个最短的整数时间 $t \ge 0$ ，使得我们能够找到一种方案，用我们的 $n$ 个堡垒，同时占领所有 $n$ 个敌人的堡垒。如果无论如何都做不到，就要告诉小 C "Can't win!"，好可怜的喵...

解题思路分析

这道题要求我们找到“最短用时”，一看到“最小化某个值”或者“最大化某个值”这样的字眼，我的直觉就告诉我，这很可能是二分答案的信号哦，喵~！

我们可以对时间 $t$ 进行二分查找。假设我们猜一个时间 $T$ ，然后我们需要一个函数 check(T) 来判断，在 $T$ 这个时刻，我们是否有可能占领所有敌方堡垒。

如果 check(T) 返回 true，说明时间 $T$ 是可行的，那么我们就可以尝试一个更短的时间，说不定有更优的解呢！于是我们把搜索区间的右边界缩小。如果 check(T) 返回 false，说明时间 $T$ 太短了，我们的堡垒还没成长到足够强大，那就需要更多的时间。于是我们把搜索区间的左边界扩大。

通过这样不断地二分，我们就能逼近那个最短的可行时间啦！

那么，核心问题就变成了如何实现 check(T) 函数，对吧？

在给定的时间点 $T$ ，所有 $2n$ 个堡垒的战斗力都是一个确定的值 $w_i(T) = k_i \cdot T + b_i$ 。问题就简化为：我们有 $n$ 支战斗力已知的部队，和 $n$ 个战斗力已知的敌方堡垒，我们能否找到一个一对一的匹配，让我们每支部队都能打败它对应的那个敌方堡垒呢？

这听起来像一个匹配问题，但其实可以用一个非常简单的贪心策略来解决，喵~

贪心策略： 为了让我们实力较弱的堡垒也能找到可以战胜的对手，最明智的做法就是让我们最强的堡垒去挑战最强的敌人。如果连我们最强的堡垒都打不过敌方最强的堡垒，那情况就糟了。反之，如果能打过，那这个最强的堡垒就完成了它的使命，剩下的堡垒就可以在剩下的敌人中进行匹配了。

这个思想可以推广开来：将我们的 $n$ 个堡垒在时刻 $T$ 的战斗力从高到低排序，得到 $Our_1, Our_2, \dots, Our_n$ 。将敌人的 $n$ 个堡垒在时刻 $T$ 的战斗力也从高到低排序，得到 $Enemy_1, Enemy_2, \dots, Enemy_n$ 。

一个可行的匹配方案存在的充要条件是：对于所有的 $i=1, \dots, n$ ，都有 $Our_i \ge Enemy_i$ 。也就是说，我们第 $i$ 强的堡垒，必须能打败敌人第 $i$ 强的堡垒。

一个更优雅的视角（括号匹配思想）：

我们可以把这个问题看得更抽象一点点，像是在玩括号匹配游戏！

把我们的 $n$ 个堡垒看作是 +1 的增益。
把敌人的 $n$ 个堡垒看作是 -1 的消耗。
将这 $2n$ 个堡垒（无论敌我）在时刻 $T$ 的战斗力全部计算出来，然后将它们从大到小一起排序。如果战斗力相同，我们应该优先处理敌人（-1），这样会让条件更苛刻，保证解的正确性。
我们从头到尾（从战斗力最高到最低）遍历这个排好序的列表，并维护一个计数器 available_troops。
- 遇到我们的堡垒（+1），就 available_troops++，表示我们多了一个可用的强大兵力。
- 遇到敌人的堡垒（-1），就 available_troops--，表示我们需要消耗一支兵力去占领它。
在整个遍历过程中，如果 available_troops 任何时刻掉到了 $0$ 以下，就说明在当前这个战斗力水平，我们遇到的敌人比我们拥有的、比它更强的堡垒还要多，GG了喵~ 这种情况下，check(T) 就返回 false。
如果顺利遍历完整个列表，available_troops 始终没有小于 $0$ ，那就说明我们总有足够的兵力去解决相应强度的敌人，check(T) 返回 true！

这种方法既直观又高效，我们就用它来实现 check(T) 函数吧！

注意点： $k_i$ 和 $b_i$ 的范围不小，而时间 $t$ 的二分上界也可能很大（比如 $2 \cdot 10^9$ ），所以计算 $k_i \cdot t + b_i$ 的时候，结果可能会超出 32 位整型（int）的范围。一定要用 long long 来存储战斗力，不然就会因为溢出而得到错误的答案哦！

代码实现

下面就是我精心为大家准备的代码啦，注释写得很详细，希望能帮到你，喵~

cpp

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

// 用一个结构体来存储堡垒的属性 k 和 b，更清晰喵~
struct Fortress {
    long long k, b;
    int type; // +1 代表我们的堡垒，-1 代表敌人堡垒
};

// 用于排序的结构体，存储特定时间的战斗力和堡垒类型
struct BattleUnit {
    long long power;
    int type;

    // 自定义排序规则
    // 战斗力高的排前面；战斗力相同时，敌人(-1)优先，这样检查更严格
    bool operator<(const BattleUnit& other) const {
        if (power != other.power) {
            return power > other.power;
        }
        return type < other.type;
    }
};

int n;
std::vector<Fortress> fortresses;

// check 函数，判断在时间 T 是否能取得胜利
bool check(long long time) {
    std::vector<BattleUnit> units;
    // 计算在 time 时刻，所有堡垒的战斗力
    for (int i = 0; i < 2 * n; ++i) {
        long long current_power = fortresses[i].k * time + fortresses[i].b;
        units.push_back({current_power, fortresses[i].type});
    }

    // 按照战斗力从高到低排序
    std::sort(units.begin(), units.end());

    int available_garrisons = 0; // 可用的驻军数量
    for (const auto& unit : units) {
        available_garrisons += unit.type;
        // 如果在任何时候，需要的驻军（敌人）比可用的还多，就说明失败了
        if (available_garrisons < 0) {
            return false;
        }
    }

    // 如果能顺利遍历完，说明可以找到匹配方案
    return true;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;
    fortresses.resize(2 * n);

    // 先读入 n 个我方堡垒
    for (int i = 0; i < n; ++i) {
        std::cin >> fortresses[i].k >> fortresses[i].b;
        fortresses[i].type = 1;
    }
    // 再读入 n 个敌方堡垒
    for (int i = n; i < 2 * n; ++i) {
        std::cin >> fortresses[i].k >> fortresses[i].b;
        fortresses[i].type = -1;
    }

    long long left = 0, right = 2000000000, ans = -1; // 时间上界要开得足够大

    // 二分答案
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (check(mid)) {
            // 如果 mid 时间可行，说明可能还有更优解（时间更短）
            ans = mid;
            right = mid - 1;
        } else {
            // 如果 mid 时间不可行，需要更长的时间
            left = mid + 1;
        }
    }

    if (ans != -1) {
        std::cout << ans << "\n";
    } else {
        std::cout << "Can't win!\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N \log R)$ 我们对时间 $t$ 进行二分查找，搜索范围是 $[0, R]$ （这里 $R$ 我们取了 $2 \cdot 10^9$ ），二分的次数是 $O(\log R)$ 。在每次二分的 check 函数中，我们需要对 $2N$ 个堡垒进行排序，这部分的复杂度是 $O(N \log N)$ 。所以总的时间复杂度就是这两者相乘，即 $O(N \log N \log R)$ ，完全可以接受的说！
空间复杂度: $O(N)$ 我们在 check 函数中创建了一个 units 向量来存储 $2N$ 个堡垒的战斗力信息，占用了 $O(N)$ 的额外空间。除此之外没有其他大的空间开销了，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然名字叫“简单题”，但其实融合了好几个重要的思想呢，喵~

二分答案: 解决“求最小的可能值/最大的可能值”这类问题的强大武器。将求解问题转化为判定问题。
贪心算法: 在 check 函数中，我们通过排序和“括号匹配”的思想，找到了一个简单而高效的判定方法。这背后是贪心的思想：用我们最强的资源去应对最严峻的挑战。
排序: 贪心策略的实现往往依赖于排序，将问题转化为有序的状态，能极大地简化决策过程。
注意数据范围: 在算法竞赛中，对数据范围和潜在的整数溢出保持警惕，是每个合格的程序员（和我！）必备的素养哦！long long 大法好！

希望这篇题解能帮助你更好地理解这道题！继续加油，你一定可以成为很棒的算法大师的，喵~！

[NCT058C2]简单题 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​