P1168 中位数

2018-06-17 22:21:35来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

给出一个长度为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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1341 无序字母对

下一篇:poj3264