洛谷 P1168 中位数

　　　　　　　　　　　　　　　　洛谷 P1168 中位数

题目描述

给出一个长度为 $A_i ，对于所有 1 ≤ k ≤ (N + 1) / 2 ，输出 A_1, A_3, …, A_{2k - 1}的中位数。即前 1,3,5,…个数的中位数。$

输入输出格式

输入格式：

第

第 $A_i (A_i ≤ 10^9) 。$

输出格式：

共 $A_1, A_3, …, A_{2k - 1}的中位数。$

输入输出样例

输入样例#1：

7
1 3 5 7 9 11 6

输出样例#1：

说明

对于

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,a[100001];
 6 int main(){
 7 //    freopen("std.in","r",stdin);
 8 //    freopen("stdt.out","w",stdout);
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)
11         scanf("%d",&a[i]);
12     for(int i=1;i<=n/2+n%2;i++){
13         sort(a+1,a+i*2);
14         printf("%d
",a[i]);
15     }
16 //    fclose(stdin);
17 //    fclose(stdout);
18     return 0;
19 }

40分暴力

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<vector>
 5 int n,a,b,m;
 6 std::priority_queue<int> vis;
 7 std::priority_queue<int,std::vector<int>,std::greater<int> > dis;
 8 int main() {
 9     scanf("%d%d",&n,&m);
10     printf("%d
",m);
11     vis.push(m);
12     for(int i=1; i<=(n-1)/2; i++) {
13         scanf("%d%d",&a,&b);
14         if(a>=m) dis.push(a); else vis.push(a);
15         if(b>=m) dis.push(b); else vis.push(b);
16         while(vis.size()>=dis.size()) { dis.push(vis.top()); vis.pop(); }
17         while(dis.size()>vis.size()+1) { vis.push(dis.top()); dis.pop(); }
18         m=dis.top();
19         printf("%d
",m);
20     }
21     return 0;
22 }

善用queue，大小根堆

明明看到了也不回复，你不知道我的心碎。