题解：SP16281 TAP2013G - War

woshizhangchi123 · 2025-07-18 16:44:19 · 题解

题目大意

给定长为 S 的数组 Q 和 N，求对 N 数组合理排序后，对两个数组每一位进行比较，使得对于任意一个 i，N_{i} > Q_{i} 的情况最多。

题目分析

此题一眼就是贪心。
首先先对两个数组从小到大排序。
接下来枚举 N 中的每个元素，与 Q 的第 k 位进行比较，若前者大于后者，则将答案加 1，并将 k 加 1。这样操作可以保证尽可能把 Q 数组中最小的几个消掉，使得答案尽可能大。

Code

#include <bits/stdc++.h>
#define N 201000
#define int long long
using namespace std;
int sum=1,ans,a[N],b[N],n;
signed main() {
    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);
    for(int i=1;i<=n;i++){
        if(b[i]>a[sum]){
            ans++;
            sum++;
        }
    }
    cout<<ans;
}

AC记录。