洛谷P7072 CSP-J 2020 直播获奖 题解

题目分析

题目传送门 由于最大数据n=10^5,普通的排序会TLE，所以可以考虑桶排序。 此处默认大家都会桶排序，我就不废话了哈 如果有不会的，可以放弃看一下这个链接，感觉这个作者讲的很好。

思路拆分

因为是输入一个数据就输出一个分数线，所以我们要在一个循环里做完读入，排序，计算分数线三个事。

cin>>n>>w;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;//读入数据

接下来就是重头戏：桶排+计算 先是桶排：

a[x]++;

接下来是计算前多少名能获奖：

int y=max(1,i*w/100);

（因为每一次都要有分数线，所以y在1与i*w/100之间取最大值）（i为当前人数）

最后是确定分数线：

cnt=0;
for(int j=600;j>=0;j—)//把桶倒序遍历，从大往小扫描
{
if(a[j]!=0)//排除无用桶
{
cnt+=a[j];//计数
if(cnt>=y)//数到获奖人数
{
cout<<j<<" ";//输出
break;//结束，进行下一个读入
}
}
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
int n,w,cnt;
int a[605];
int main()
{
cin>>n>>w;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++;
int y=max(1,i*w/100);
cnt=0;
for(int j=600;j>=0;j—)
{
if(a[j]!=0)
{
cnt+=a[j];
if(cnt>=y)
{
cout<<j<<" ";
break;
}
}
}
}
return 0;
}