对线压制 - 贪心算法经典例题 - C++代码实现 - 常规

对线压制 - 贪心算法经典例题

题目描述

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

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

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

输入格式

第一行输入两个正整数 $n,k$（$k\le n\le1000$）。

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

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

输出格式

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

样例 #1

样例输入 #1

5 32 4 6 8 109 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\le n\le1000,1\le a_i,b_i\le10^6$。

C++代码实现cpp#include#includeusing namespace std;const int N=1005;int a[N],b[N];int main(){ int n,k; cin>>n>>k; 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,i=1,j=1; while(i<=n&&j<=n){ if(a[i]>b[j]) { ans++; i++; j++; } else { i++; } } if(ans>=k) cout<<'YES'<<endl; else cout<<'NO'<<endl; return 0;}

解题思路

本题可以使用贪心算法解决。为了让红方尽可能多地获得对线压制，我们可以采取以下策略：

排序: 将红方和蓝方的选手能力值分别从小到大排序。2. 贪心匹配: 从双方能力值最小的选手开始匹配。如果红方选手能力值更高，则红方获得对线压制，并将双方选手都排除。否则，只将红方选手排除，继续匹配下一位红方选手。

这个策略的贪心之处在于，每次匹配都优先考虑让能力值较低的红方选手获得胜利，从而尽可能地保留能力值更高的红方选手去挑战能力值更高的蓝方选手。

代码解释

sort(a+1,a+n+1) 和 sort(b+1,b+n+1) 分别对红方和蓝方的选手能力值进行排序。* while(i<=n&&j<=n) 循环遍历红方和蓝方的选手。* if(a[i]>b[j]) 判断当前红方选手是否可以战胜当前蓝方选手。如果可以，则红方获得一分，并将双方选手都排除。* else 如果当前红方选手不能战胜当前蓝方选手，则只将红方选手排除，继续匹配下一位红方选手。* 最后根据红方获得的胜利次数是否大于等于 k 来输出结果。

希望本题解能帮助您更好地理解和掌握贪心算法。