4145: 直播获奖（live）
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：14
解决：2
题目描述
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 ，即当前排名前 的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了 个选手的成绩，则当前计划获奖人数为 ，其中 是获奖百分比， 表示对 向下取整， 表示 和 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
输入
第一行有两个整数 。分别代表选手总数与获奖率。
第二行有 个整数，依次代表逐一评出的选手成绩。
输出
只有一行，包含 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
样例输入 复制
10 60
200 300 400 500 600 600 0 300 200 100样例输出 复制
200 300 400 400 400 500 400 400 300 300提示
样例 1 解释
注意，在第 9 名选手的成绩评出之后，计划获奖人数为 5 人，但由于有并列，因此实际会有 6 人获奖。
数据规模与约定
各测试点的 如下表：
| 测试点编号 | |
|---|---|
对于所有测试点，每个选手的成绩均为不超过 的非负整数，获奖百分比 是一个正整数且 。
提示
在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float 、 double，Pascal 中的 real 、 double 、 extended 等）存储获奖比例 ，则计算 时的结果可能为 ，也可能为 ，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。
#include<bits/stdc++.h>
using namespace std;
/*
1.获奖人数为k = max(1, int(p × w%))
2.选手的成绩均为不超过 600 的非负整数
思路：使用数组统计每个分值得分的人数
从大到小统计出k个人，最后一次循环对应的分值就是要求的获奖分数
*/
int a[610];
int n,w,x;
int main(){
scanf("%d%d",&n,&w);
int k;//获奖人数
int ans;//统计人数
//读入n个人的分数，读一个算一个
for(int i = 1;i <= n;i++){
scanf("%d",&x);
a[x]++;//统计每个分值对应的人数
//计算获奖人数
k = max(1,int(i * w / 100.0));
ans = 0;
//从最高分的人数向下统计出>=k个人
for(int j = 600;j >= 0;j--){
if(ans + a[j] < k) ans += a[j];//+=
else{
printf("%d ",j);
break;
}
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
//解法2:计数排序原理-时间复杂度-O(n)
const int N=1e5+10;
int n,w,a[N],b[N];
int main(){
cin>>n>>w;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[a[i]]++; //统计a[i]这个分数的人数
int r=i*w/100; //计划获奖人数
for(int j=600;j>=0;j--) {
if (b[j]) {
if (r<=b[j]){
cout<<j<<" ";
break;
}else {
r-=b[j];
}
}
}
}
return 0;
}