题解
对顶堆技巧。
就是把序列拆成两个部分，使得要维护的特定的数恰好处于被堆分割的部分。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
58
59
60
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
priority_queue<int, vector<int>, greater<int> > pq1;
priority_queue<int> pq2;
int n;
void init(){
int snum = read();
n = read();
printf("%d %d\n", snum, (n + 1) >> 1);
}
void solve(){
if(n == 1){
printf("%d", read());
return ;
}
int hd = read(), cnt = 2;
printf("%d ", hd);
pq2.push(hd);
for(int i = 2; i <= n; ++i){
hd = read();
if(hd <= pq2.top()) pq2.push(hd);
else pq1.push(hd);
if(i & 1){
while(pq2.size() > pq1.size() + 1)
pq1.push(pq2.top()), pq2.pop();
while(pq2.size() < pq1.size() + 1)
pq2.push(pq1.top()), pq1.pop();
printf("%d", pq2.top());
if(cnt == 10 && i != n)
cnt = 0, printf("\n");
else if(i != n) printf(" ");
cnt++;
}
}
while(!pq1.empty()) pq1.pop();
while(!pq2.empty()) pq2.pop();
}
int main(){
int T = read();
for(int i = 1; i <= T; ++i){
init();
solve();
if(i != T) printf("\n");
}
return 0;
}