对线压制 - 算法题解：贪心策略求解红方是否能获得足够对线压制

题目描述

峡谷里有 n 条线路，红蓝双方分别有 n 位选手，双方每位选手都要前往一条线路参与对线，每条线路上恰好有红蓝方各一位选手。

红色方每位选手的对线能力为 a_i，蓝色方每位选手的对线能力为 b_i，在一条线路上，能力值更高的那位选手可以获得这条线路的'对线压制'，能力值相同则互不压制。

红方教练想要知道是否有存在一种对阵情况，使得红方可以获得至少 k 条路的'对线压制'。

输入格式

第一行输入两个正整数 n,k（k≤n≤1000）。

第二行输入 n 个正整数 a_i（a_i≤10^6），表示红方选手的能力值。

第三行输入 n 个正整数 b_i（b_i≤10^6），表示蓝方选手的能力值。

输出格式

如果存在一种对阵情况，使得红方可以获得至少 k 条路的'对线压制'，则输出“YES”。否则输出'NO'。

样例 #1

样例输入 #1

5 3
2 4 6 8 10
9 7 5 3 1

样例输出 #1

YES

提示

| 胜方 | 红 | 红 | 蓝 | 红 | 红 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 红 | 2 | 4 | 6 | 8 | 10 | | 蓝 | 1 | 3 | 7 | 5 | 9 |

在这种对位情况下，红方可以获得 4 条路的对线压制，大于 3。

所以输出YES。

子任务

对于 30% 的数据，a_i>b_i；

对于 100% 的数据，k≤n≤1000,1≤a_i,b_i≤10^6。

贪心策略

为了使红方获得尽可能多的对线压制，我们可以使用贪心策略：

**排序：**将红方选手的能力值 a_i 从小到大排序，将蓝方选手的能力值 b_i 从大到小排序。
**匹配：**从红方能力值最小的选手开始，依次与蓝方能力值最大的选手进行匹配。
**计数：**如果红方选手的能力值小于蓝方选手的能力值，则红方获得一条路线的对线压制，计数器加 1。

通过这种贪心策略，我们确保了红方每次都能选择最有利的对阵，从而最大化对线压制的数量。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int a[n], b[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(a, a + n);
    sort(b, b + n, greater<int>());
    int count = 0;
    for (int i = 0; i < k; i++) {
        if (a[i] < b[i]) {
            count++;
        }
    }
    if (count >= k) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

代码解析：

**排序：**使用 sort 函数分别对红方和蓝方选手的能力值进行排序。
**匹配：**通过循环遍历红方和蓝方选手，依次进行匹配，并判断红方是否获得对线压制。
**计数：**使用 count 变量记录红方获得的对线压制数量。
**输出：**根据 count 的值判断红方是否获得至少 k 条路线的对线压制，输出相应的结果。

总结

这道题可以通过贪心策略来解决，将红方和蓝方选手按照能力值进行排序，然后依次匹配，以最大化红方获得的对线压制数量。代码实现简洁，易于理解，体现了贪心算法的灵活性和实用性。