题目内容
33DAI 最近喜欢玩《骑马与砍杀 2》，他正领导着一支\(n\)人的小队（保证\(n\)是偶数），小队成员编号\(1\backsim n\)。他们中编号为 \(i\)的成员（\(1\le i\le \frac{n}{2}\) ）与编号为\(i+\frac{n}{2}\)的成员互为朋友关系。
为了掩护主力撤退，他决定选择其中\(k\) 名成员留下拖住敌人。显然选择的人不同，能拖住敌人的时间不一样。33DAI 提前了解过：
编号为\(i\) 的成员如果朋友没有被留下，就有把敌人拖住\(a_i\) 秒的能力，
否则如果他的朋友和他一起被留下了，就只能把敌人拖住\(b_i\) 秒的能力
保证\(b_i\le a_i\)
最终拖住敌人的时间为每个被留下成员拖住敌人的能力之和。
请你算算怎么选择能把敌人拖住最久，输出最久的时间。
解题思路
显然，对于每一对，都有四种方案：都不留；标号较小的朋友留；编号较大的朋友留；两个都留。
其中第二种方案和第三种方案可归结为留下\(a_i\)较大的朋友。
于是我们可以对于所有\(1\le i\le \frac{n}{2}\)，设\(\frac{n}{2}+i=j\)。
把\(max(a_i,a_j)\)和\(b_i+b_j-max(a_i,a_j)\)丢进一个大根堆里，选择前\(k\)个。
如果只选择了\(max(a_i,a_j)\)，就相当于第二和第三种方案。
如果选择了\(b_i+b_j-max(a_i,a_j)\)和\(max(a_i,a_j)\)，就相当于第四种方案。
如果俩都没选，就相当于第一种方案。
注意到这里不能选择\(b_i+b_j-max(a_i,a_j)\)而不选择\(max(a_i,a_j)\)，因为\(2max(a_i,a_j)\ge a_i+a_j\ge b_i+b_j\)，但是如果取等的话那样也就相当于选择了\(max(a_i,a_j)\)
代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<int> p;
int n,m,i,j,a[5003],b[5003],ans;
int main()
{cin>>n>>m;for(i=1;i<=n;i++) scanf("%d",&a[i]);for(i=1;i<=n;i++) scanf("%d",&b[i]);for(i=1;i<=n/2;i++){p.push(max(a[i],a[i+n/2]));p.push(b[i]+b[i+n/2]-max(a[i],a[i+n/2]));}while(m--){ans+=p.top();p.pop();}cout<<ans;
}