P1168 中位数
2018-06-17 22:21:35来源:未知 阅读 ()
题目描述
给出一个长度为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]的中位数。
输入输出样例
7 1 3 5 7 9 11 6
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
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- 寻找两个有序数组的中位数 2020-04-09
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash