問題文
N を 1 以上の整数とします。
長さ 3N の数列 a=(a1,a2,…,a3N) があります。 すぬけ君は、a からちょうど N 個の要素を取り除き、残った 2N 個の要素を元の順序で並べ、長さ 2N の数列 a' を作ろうとしています。 このとき、a' のスコアを (a'の前半N要素の総和)−(a'の後半N要素の総和) と定義します。
a' のスコアの最大値を求めてください。
制約
1≤N≤105
ai は整数である。
1≤ai≤109
部分点
300 点分のテストケースでは、N≤1,000 が成り立つ。
入力
入力は以下の形式で標準入力から与えられる。
N
a1 a2 … a3N
出力
a' のスコアの最大値を出力せよ。
入力例 1
Copy
2
3 1 4 1 5 9
出力例 1
Copy
1
a2, a6 を取り除くと、a'=(3,4,1,5) となり、スコアは (3+4)−(1+5)=1 となります。
入力例 2
Copy
1
1 2 3
出力例 2
Copy
-1
例えば、a1 を取り除くと、a'=(2,3) となり、スコアは 2−3=−1 となります。
入力例 3
Copy
3
8 2 2 7 4 6 5 3 8
出力例 3
Copy
5
例えば、a2, a3, a9 を取り除くと、a'=(8,7,4,6,5,3) となり、スコアは (8+7+4)−(6+5+3)=5 となります。
题意： 给出3n个数，让你去掉n个数，使剩下的前n个数的和减去后n个数的和的差最大，求这个差
题解：很容易可以写出O（n^3）的状态转移方程，然后考虑优化，可以用优先队列把O(n^2)压缩成O（logn）的，详情见代码
代码如下：
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std; int n;
long long dp1[],dp2[],a[],sum1,sum2; priority_queue<long long,vector<long long>,greater<long long> > q;
priority_queue<long long> q2; int main()
{
//fuck!!!
scanf("%d",&n);
memset(dp1,,sizeof(dp1));
memset(dp2,0x3f,sizeof(dp2));
for(int i=;i<=*n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=;i<=n;i++)
{
q.push(a[i]);
sum1+=a[i];
}
dp1[n]=sum1;
for(int i=n+;i<=*n;i++)
{
if(q.top()<a[i])
{
sum1-=q.top();
sum1+=a[i];
q.pop();
q.push(a[i]);
}
dp1[i]=sum1;
}
for(int i=*n;i>*n;i--)
{
q2.push(a[i]);
sum2+=a[i];
}
dp2[*n+]=sum2;
for(int i=*n;i>=;i--)
{
if(q2.top()>a[i])
{
sum2-=q2.top();
sum2+=a[i];
q2.pop();
q2.push(a[i]);
}
dp2[i]=sum2;
}
long long ans=-0x3f3f3f3f3f3f3f3f;
for(int i=n;i<=*n;i++)
{
ans=max(ans,dp1[i]-dp2[i+]);
}
printf("%lld\n",ans);
}