首页 > 代码库 > 3N Numbers
3N Numbers
D - 3N Numbers
Time limit : 2sec / Memory limit : 256MB
Score : 500 points
Problem Statement
Let N be a positive integer.
There is a numerical sequence of length 3N, a=(a1,a2,…,a3N). Snuke is constructing a new sequence of length 2N, a‘, by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a‘ is defined as follows: (the sum of the elements in the first half of a‘)−(the sum of the elements in the second half of a‘).
Find the maximum possible score of a‘.
Constraints
- 1≤N≤105
- ai is an integer.
- 1≤ai≤109
Partial Score
- In the test set worth 300 points, N≤1000.
Input
Input is given from Standard Input in the following format:
Na1 a2 … a3NOutput
Print the maximum possible score of a‘.
Sample Input 1
23 1 4 1 5 9Sample Output 1
1When a2 and a6 are removed, a‘ will be (3,4,1,5), which has a score of (3+4)−(1+5)=1.
Sample Input 2
11 2 3Sample Output 2
-1For example, when a1 are removed, a‘ will be (2,3), which has a score of 2−3=−1.
Sample Input 3
38 2 2 7 4 6 5 3 8Sample Output 3
5
For example, when a2, a3 and a9 are removed, a‘ will be (8,7,4,6,5,3), which has a score of (8+7+4)−(6+5+3)=5.
/// 题意是:有一个 3n 长的序列，现拿走 n 个数，然后分成前 n 个数，和后 n 个数 ，求前n个数和减后 n 个数和的最大值
// 用一个优先队列保存区间最大 n 数和，并赋给数组保存
用一个优先队列保存区间最小 n 数和，并赋给数组保存
最后循环一遍即可
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define INF (1LL<<62) 5 #define MX 100005*3 6 7 LL a[MX]; 8 LL ma[MX]; 9 LL mi[MX];10 11 int main()12 {13 LL n;14 cin>>n;15 16 for (int i=1;i<=3*n;i++)17 scanf("%lld",&a[i]);18 priority_queue <LL> Q;19 LL sum = 0;20 for (int i=1;i<=2*n;i++)21 {22 Q.push(-a[i]);23 sum+=a[i];24 25 if (i>n) sum += Q.top(),Q.pop();26 ma[i]=sum;27 }28 29 while (!Q.empty()) Q.pop();30 sum=0;31 for (int i=3*n;i>=n+1;i--)32 {33 Q.push(a[i]);34 sum+=a[i];35 36 if (i<=2*n) sum -= Q.top(),Q.pop();37 mi[i]=sum;38 }39 40 LL ans = -INF;41 for (int i=n;i<=2*n;i++)42 ans = max (ans, ma[i]-mi[i+1]);43 cout<<ans<<endl;44 return 0;45 }
3N Numbers