牛客2020寒假训练营6-A

牛客2020寒假训练营6-A

七月 15, 2020

配对

题意

现在有正整数集合 A 和 B，每个集合里有 N 个数，你要建立他们间的一一映射 将每对配对的数字相加可以得到 N 个和，你要做的就是最大化第 K 大的和

题解

我们要使得第K大的和尽可能大，显然可以贪心：
首先，组成这K对数字的显然是A中最大的K个数字和B中最大的K个数字。
问题转化为怎样配对使得最小的和最大：

如果k=2
那么 将a1+b2，a2+b1作为前k大的数那么 能让k=2最大
经过简单的归纳可以得到，倒序配对是最优的，这样就解决了问题
即a1+bk ,a2+bk-1….. ak+b1中选第k大最优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=(ll)1e9+7;
int a[(int)1e5+4],b[(int)1e5+4];
int  main(){
    int n,m;cin>>n>>m;
    vector<int>ans;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    for(int i=n-m+1,j=n;i<=n;i++,j--){
        ans.push_back(a[i]+b[j]);
        //cout<<a[i]<<" "<<b[j]<<endl;
    }
    sort(ans.begin(),ans.end());
    reverse(ans.begin(),ans.end());
    cout<<ans[m-1]<<endl;
}