3out1in

题目链接

题目大意

这是codechef starter 134 div4的第五题。

给你一个数组B，里面包含M个数字，其中M必定为奇数。操作是选出三个数字a,b,c, 这三个数字从数组里剔除，数组中重新加入成员a+b-c。可以看出来每一次操作会让数组少两个元素，问最后剩下一个元素的最大值是多少。其中有多个询问，询问内容是如果只有前k个元素，剩下的最后一个元素最大值是多少。

赛时回顾

我在第一次做这道题的时候就直接考虑到了用优先队列。显然最优解是每次选两个最大值，然后减去最小值。原数组我用数组a存储，每次将前k个元素送入优先队列和数组b中，数组b进行排序用来获得最小值，优先队列获取最大值。成功拿到30分的部分分，其他测试会超时。

正解

官方题解思路让我恍然大悟。永远记得可以用空间换取时间。既然可以用一个优先队列，那么我们就可以用两个优先队列。虽然我们不知道给出的qurey里k的值是多少，但是我们可以用ans数组记录所有对应k值的答案。

首先就要考虑随着数组元素的增加，状态是如何转移的。我们可以将现有元素分成两组，一个是samll组，一个是large组。small组是所有会被减去的数字，large组是所有会被加上的数字。每次需要两个large组的元素相加，一个small组的元素被减，但是得到的数字还应该被保留在large数组里。可以推断出，large数组元素个数应该永远比small数组多1。

事实上我们并不需要将真的每次操作得到的数字压到优先队列里面。因为每个数字只有两种可能，被赋予加号，代表和其他元素相加，被赋予减号，代表被减去。符号确定后所有元素的和是不会变的。我们只需要计算现在small组里元素的总和sumin，large组里元素的总和sumax，然后答案就是sumax-sumin。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxlen = 2e5+10;
int a[mxlen];
ll ans[mxlen];
int n,q;

void work(){
    priority_queue<ll> pqmin;
    priority_queue<ll> pqmax;
    ll sumin = 0;
    ll sumax = 0;
    for(int i=1;i<=n;i++){
        pqmin.push(a[i]);
        sumin+=a[i];
        //这里表达式的意思是pqmin.size()要永远少一个
        while(pqmin.size()>=pqmax.size()){
            ll mi = pqmin.top();
            pqmin.pop();
            pqmax.push(-mi);
            sumax+=mi;
            sumin-=mi;
        }
        while(!pqmin.empty()&&pqmin.top()>-pqmax.top()){
            ll mi = pqmin.top();
            ll ma = -pqmax.top();
            pqmin.pop(); pqmax.pop();
            pqmin.push(ma);
            pqmax.push(-mi);
            sumin = sumin-mi+ma;
            sumax = sumax-ma+mi;
        }
        
        ans[i]=sumax-sumin;
    }
}
int main() {
	int T;
	cin>>T;
	while(T--){
	    
	    cin>>n>>q;
	    for(int i=1;i<=n;i++){
	        cin>>a[i];
	    }
        work();
	    for(int i=1;i<=q;i++){
	        int k;
	        cin>>k;
            cout<<ans[k]<<" ";
	    }
	}
	
    return 0;
}