挑战赛#21 T2 题解 100% AC

算法思路详解

‌1. 问题分析‌：

• 这是一个典型的贪心算法问题，需要找到小午卡片的最佳匹配策略
• 小枫的出牌顺序已知（排序后），小午需要选择自己的牌来最大化获胜次数
• 平局算小枫获胜，所以小午必须使用比小枫当前牌严格大的牌才能获胜

‌2. 关键策略‌：

• 排序‌：将双方的卡片都按升序排序，这样可以方便地找到最佳匹配
• 贪心匹配‌：对于小枫的每一张牌（从小到大），用小午手中比它大的最小牌来应对，这样可以保留更大的牌应对小枫后面更大的牌

3‌. 时间复杂度‌：

• 排序的时间复杂度是$O(n log n)$
• 匹配过程是$O(n)$的线性扫描
• 总时间复杂度为$O(n log n)$，对于$n≤10^6$是可行的

4‌. 边界情况处理‌：

• 当所有牌点数相同时，小午无法获胜（输出NO）
• 当小午的牌都小于等于小枫的牌时，也无法获胜

5‌. 为什么这个策略最优‌：

• 通过使用最小的足够大的牌来应对小枫的牌，可以保留更大的牌应对小枫后面更大的牌
• 这种策略确保了我们不会"浪费"大牌去应对小枫的小牌

6‌. 胜负判断‌：

• 小午需要赢超过$n/2$轮才能获胜
• 因为平局算小枫赢，所以小午必须赢的轮数 $> n -$ 赢的轮数

这个算法巧妙地利用了排序和贪心策略，确保在最优情况下计算小午能否获胜。

#include <bits/stdc++.h>
using namespace std;

int a[1000010], b[1000010];  // 定义两个数组存储卡片点数，a是小枫的卡片，b是小午的卡片

int main() {
    int n;  // 卡片数量
    cin >> n;  // 输入卡片数量
    
    // 输入小枫的卡片点数
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 输入小午的卡片点数
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    
    // 对小枫和小午的卡片进行排序（升序）
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    
    int ans = 0;  // 记录小午能赢的轮数
    int j = 1;     // 小午卡片的指针
    
    // 遍历小枫的每一张卡片（从小到大）
    for(int i = 1; i <= n; i++) {
        // 找到小午手中比小枫当前卡片大的最小卡片
        while(j <= n && b[j] <= a[i]) {
            j++;
        }
        
        // 如果找到这样的卡片
        if(j <= n) {
            ans++;  // 小午赢一轮
            j++;    // 这张卡片已经使用过，指针后移
        }
    }
    
    // 判断小午是否能获胜（赢的轮数超过一半）
    if(ans > n - ans) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    
    return 0;
}