题解：SP16281 TAP2013G - War

题目大意

给定长为

S

的数组

Q

和

N

，求对

N

数组合理排序后，对两个数组每一位进行比较，使得对于任意一个

i

，

N_{i} > Q_{i}

的情况最多。

题目分析

此题一眼就是贪心。
首先先对两个数组从小到大排序。
接下来枚举

N

中的每个元素，与

Q

的第

k

位进行比较，若前者大于后者，则将答案加

1

，并将

k

加

1

。这样操作可以保证尽可能把

Q

数组中最小的几个消掉，使得答案尽可能大。

Code

CPP

#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记录。

题解：SP16281 TAP2013G - War

文章操作

题目大意

题目分析

Code

相关推荐

评论

题解：SP16281 TAP2013G - War