题目的意思是,给你一个长为3N的序列,从中删除N个序列,将剩下的2N个序列平分后用前面的区间和减去后面的区间和,求最大的区间差。

竟然考的是优先队列,真的是尴尬,还有输出要是%lld或者是cout。

我的想法就是至少要在n-2n后面切开这段序列,然后前面一段排序后删除最小数,后面一段排序后删除最大数,一直排序肯定不行,所以用优先队列优化,开始还打算手写链表来着。。。


代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f;
typedef long long LL;
const int maxn=100005;
LL p1[maxn], p2[maxn];
int n,res[maxn*3];
LL c1, c2, ans;
priority_queue<int, vector<int>, greater<int> > Q1;
priority_queue<int> Q2;
int main()
{
    scanf("%d", &n);
    c1=c2=0;
    for(int i=1;i<=3*n;i++){
        scanf("%lld", &res[i]);
        if(i<=n){
            Q1.push(res[i]);
            c1+=res[i];
        }
        else if(i>2*n){
            Q2.push(res[i]);
            c2+=res[i];
        }
    }
    p1[0]=c1;
    p2[0]=c2;
    for(int i=1;i<=n;i++){
        c1+=res[n+i];
        Q1.push(res[n+i]);
        c1-=Q1.top();
        Q1.pop();
        p1[i]=c1;
        c2+=res[2*n+1-i];
        Q2.push(res[2*n+1-i]);
        c2-=Q2.top();
        Q2.pop();
        p2[i]=c2;
    }
    ans=-INF;
    for(int i=0;i<=n;i++){
        ans=max(ans, p1[i]-p2[n-i]);
    }
    printf("%lld\n", ans);
    return 0;
}