题意:给出3N个点,删除其中N个点,将剩下的2N个数分成两份,求前面部分的和减去后面部分的和的最大值。


题解:设前面部分为Na,后面部分为Nb,要使Na-Nb最大。我们可以先假设这删除的N个全都是从N+1到3N中删除的。那么Na最大的就是前面N个的和,我们用最小优先队列来维护这N个的值,然后把接下来的第N+1个数push 进去,删除其中最小的这样就得到了在前N+1个中删除一个的前面的最大值了,依次类推。同理,我们用一个最大优先队列维护后面的N个值,然后往前推,这样就得到了每个区间Nb的最小值。最后循环一遍取Nai-Nbi的最大值就好。


题目:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
priority_queue<LL, vector<int>, greater<int> > l;   //最小值优先
priority_queue<LL> r;
LL lv[maxn], rv[maxn], data[maxn];
int n;
 
int main()
{
   while(~scanf("%d", &n)){
       while(!l.empty())l.pop();
       while(!r.empty())r.pop();
       LL x, ans, lsum=0, rsum=0;
       for(int i=0;i<2*n;i++){
           scanf("%lld", &x);
           data[i]=x;
           lsum+=x;
           l.push(x);
           if(i>=n-1){
               if(i>n-1){
                   lsum-=l.top();
                   l.pop();
               }
               lv[i-n+1]=lsum;
           }
       }
       for(int i=0;i<n;i++){
           scanf("%lld", &x);
           rsum+=x;
           r.push(x);
       }
       for(int i=2*n-1;i>=n-1;i--){
           rv[i-n+1]=rsum;
           r.push(data[i]);
           rsum+=data[i];
           rsum-=r.top();
           r.pop();
       }
       ans=-inf;
       for(int i=0;i<=n;i++){
           ans=max(ans, lv[i]-rv[i]);
       }
       printf("%lld\n", ans);
   }
   return 0;
}