P1168 中位数
题目描述
给出一个长度为N的非负整数序列A[i]，对于所有1 ≤ k ≤ (N + 1) / 2，输出A[1], A[3], …, A[2k - 1]的中位数。[color=red]即[/color]前1，3，5，……个数的中位数。
输入输出格式
输入格式：
输入文件median.in的第1行为一个正整数N，表示了序列长度。
第2行包含N个非负整数A[i] (A[i] ≤ 10^9)。
输出格式：
输出文件median.out包含(N + 1) / 2行，第i行为A[1], A[3], …, A[2i – 1]的中位数。
输入输出样例
输入样例#1：
7
1 3 5 7 9 11 6输出样例#1：
1
3
5
6说明
对于20%的数据，N ≤ 100；
对于40%的数据，N ≤ 3000；
对于100%的数据，N ≤ 100000。
编译都不过居然能AC
虽然也不知道怎么AC的。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<ext/pb_ds/assoc_container.hpp>
6 #include<ext/pb_ds/tree_policy.hpp>
7 #include<functional>
8 using namespace std;
9 using namespace __gnu_pbds;
10 void read(int & n)
11 {
12 char c='+';int x=0;int flag=0;
13 while(c<'0'||c>'9')
14 { c=getchar(); if(c=='-') flag=1; }
15 while(c>='0'&&c<='9')
16 {x=x*10+(c-48);c=getchar();}
17 flag==1?n=-x:n=x;
18 }
19 int main()
20 {
21 int n;int p;
22 read(n);
23 //tree<int , null_type , less_equal<int> , rb_tree_tag , tree_order_statistics_node_update>t;
24 tree<int, null_type, std::less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> t;
25 for(int i=1;i<=n;i++)
26 {
27 read(p);
28 t.insert(p);
29 if(i%2==1)
30 printf("%d\n", *t.find_by_order(i / 2 ));
31 }
32 return 0;
33 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-06-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录