admin 管理员组

文章数量: 1086019

体前屈大赛(桶排序）

试题G：体前屈大赛 20’
描述
某校的火柴部部长拟定向筋肉部发起一场特别的活动:体前屈大赛

比赛流程是:公布规则->体前屈测试->颁发奖牌

比赛规则:初始参赛人员共有nn人，已知在体前屈测试后会有qq次特殊事件tt发生:

t=1t=1类事件:中途加入一名隐藏选手，已知他的体前屈成绩为kk;
t=2t=2类事件:将所有参赛人员根据体前屈成绩从左到右升序排序，并给从左到右数第kk个选手颁发倒霉奖
注:颁发了倒霉奖牌的选手仅仅是拥有奖牌，奖牌不会影响这位选手原来的性质与作用。

体前屈测试:在体前屈测试中初始参赛人员每人都会有一个体前屈成绩ai。

颁发奖牌:你是一名有一说一的纯路人裁判，颁发奖牌的任务降临到了你的头上

在你每一次颁发奖牌时,都要报出这位倒霉的选手的体前屈成绩!

请你利用你的计算机优势,编写一个程序， 根据已知条件输出每一次颁发奖牌时, 你需要报出的成绩。

输入
第一行输入2个整数n,q；

第二行输入n个整数ai(- 1000≤ai < 1000)
第3至(q+ 2)3至(q+2)行每行输入2个整数
t,k;t=1时，-1000<=k<=1000
)

能够保证至少有一个t = 2，即不会出现没有输出的情况。

输出
对于每个t = 2输出1个整数

样例
输入复制
5 8
-1000 1000 4 -5 0
2 1
2 2
2 3
2 4
2 5
1 -1000
2 1
2 2
输出复制
-1000
-5
0
4
1000
-1000
-1000
提示
数据规模

对于100%的数据，n<=1e6,1≤q≤10000

#include <stdio.h>
#include <stdlib.h>
int n,q,a[1000005],t,k,p,w;
int main()
{scanf("%d%d",&n,&q);for(int i=0;i<n;i++){scanf("%d",&p);a[p+1000]++; }while(q--){w=0;scanf("%d%d",&t,&k);if(t==1){a[k+1000]++;			}else{for(int i=0;i<=2000;i++){if(a[i]){if(w+a[i]>=k){printf("%d\n",i-1000);break;}else{w+=a[i];}}}}}return 0;
}

本文标签： 体前屈大赛(桶排序）

版权声明：本文标题：体前屈大赛(桶排序） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693407040a220125.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。