原题大意

给3n个数，要求去掉n个数，使得剩下的2n个数里，前n个数减后n个数的值最大，求最大值。

算法分析

将球分为三种颜色，被取走的标为黑色，剩下的前n个为红色，后n个为蓝色，所以观察后发现，红色一定只出现在前面，蓝色一定只出现在后面，红色的最后一个位置是n~2n，蓝色的第一个位置一定是n+1~2n+1。设k为分界线，红球从前k个里面取，蓝球从后3*n-k里面取，k的取值为(n<=k<=2n)，枚举k的取值，用优先队列维护最优值。

程序代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<queue>
using namespace std;

priority_queue<int>QD;//大根堆
priority_queue<int,vector<int>,greater<int> >QU;//小根堆

typedef long long ll;
int n;
int a[310000];
ll pmx[310000],qmn[310000],smx,smn,ans=-(1ll<<60);

int main(){
    scanf("%d",&n);
    for(int i=1;i<=3*n;i++){
        scanf("%d",&a[i]);
    }for(int i=1;i<=n;i++){
        smx+=a[i];
        QU.push(a[i]);
    }
    pmx[n]=smx;
    for(int i=n+1;i<=2*n;i++){
        if(a[i]>QU.top()){
            smx-=QU.top();
            QU.pop();
            smx+=a[i];
            QU.push(a[i]);
        }
        pmx[i]=smx;
    }
    for(int i=3*n;i>2*n;i--){
        smn+=a[i];
        QD.push(a[i]);
    }
    qmn[2*n+1]=smn;
    for(int i=2*n;i>=n;i--){
        if(a[i]<QD.top()){
            smn-=QD.top();
            QD.pop();
            smn+=a[i];
            QD.push(a[i]);
        }
        qmn[i]=smn;
    }
    for(int i=n;i<=2*n;i++){
        ans=max(ans,pmx[i]-qmn[i+1]);
    }
    printf("%lld\n",ans);
    return 0;
}