CF Duels 题解

算法思路

核心思想

本题采用二分答案 + 贪心匹配的策略来解决。我们需要找到最少需要知道前多少个体育场的对手信息，才能确保存在一种安排方式使得我方球队获胜。

关键观察

• 总奖金固定，我方需要获得超过总奖金一半才能获胜
• 对于已知的体育场（前k个），我们知道确切的对手球员技能
• 对于未知的体育场（后n-k个），我们假设对手会以最不利于我们的方式安排球员

算法详解

1. 数据结构设计

struct node {
    int skill, val;  // skill: 对手技能, val: 奖金
    bool operator < (const node &b) const {
        return val < b.val;  // 按奖金排序（大顶堆）
    }
};
priority_queue<node> pq;  // 用于存储所有比赛信息
set<int> A;  // 存储我方球员技能

2. 核心函数 calc(x)

该函数模拟在知道前x个体育场信息的情况下，我方能够获得的最大奖金。

步骤：

1. 处理已知信息：将前x个体育场的对手信息和奖金加入优先队列
2. 处理未知信息：将剩余体育场的奖金和对手技能排序后配对，加入优先队列
3. 贪心匹配：
   • 每次选择奖金最高的比赛
   • 如果我方有能战胜对手的球员，就派出刚好能赢的最小技能球员
   • 如果没有能赢的球员，就派出最弱的球员（减少损失）

3. 二分搜索

int l = 0, r = n, res = -1;
while (l <= r) {
    int mid = (l + r) / 2;
    if (calc(mid) * 2 > all)  // 能获胜
        res = mid, r = mid - 1;  // 尝试更小的k
    else
        l = mid + 1;  // 需要更大的k
}

复杂度分析

• calc函数：

  • 排序：O(n log n)
  • 优先队列操作：O(n log n)
  • 集合操作：O(n log n)
  • 总复杂度：O(n log n)

• 二分搜索：O(log n) 次调用

• 总复杂度：O(n log² n)，对于 n ≤ 5×10⁴ 可接受

正确性证明

贪心策略的正确性

1. 按奖金降序处理：优先争取高奖金比赛，最大化收益
2. 最小技能匹配：使用刚好能赢的球员，保留强力球员应对后续比赛
3. 最坏情况假设：未知体育场采用最优配对方式对抗我方

二分答案的正确性

• 如果知道k个体育场信息就能获胜，那么知道更多信息(k+1, k+2...)也一定能获胜
• 满足二分答案的单调性条件

算法标签

• 二分答案 (Binary Search on Answer)
• 贪心算法 (Greedy Algorithm)
• 优先队列 (Priority Queue)
• 集合操作 (Set Operations)
• 排序 (Sorting)

代码亮点

1. 清晰的数据结构：使用结构体封装比赛信息
2. 高效的贪心匹配：利用set的upper_bound快速找到最小可赢球员
3. 合理的最坏情况模拟：对未知信息采用最优配对
4. 简洁的二分框架：标准二分答案模板

总结

本题通过二分答案确定最少需要的信息量，结合贪心算法在最坏情况下验证可行性，是一个典型的最优化问题转化为判定问题的思路。算法设计巧妙，充分利用了STL容器的高效操作，在合理的时间复杂度内解决了问题。