（oh!多麼美好的一天）

看題！

原題鏈接（洛谷）

[CSP-J2020] 直播獲獎

題目描述

NOI2130 即將舉行。為了增加觀賞性，CCF 決定逐一評出每個選手的成績，並直播即時的獲獎分數線。本次競賽的獲獎率為 w%，即當前排名前 w% 的選手的最低成績就是即時的分數線。

更具體地，若當前已評出了 p 個選手的成績，則當前計劃獲獎人數為 \max(1, \lfloor p * w %\rfloor)，其中 w 是獲獎百分比，\lfloor x \rfloor 表示對 x 向下取整，\max(x,y) 表示 x 和 y 中較大的數。如有選手成績相同，則所有成績併列的選手都能獲獎，因此實際獲獎人數可能比計劃中多。

作為評測組的技術人員，請你幫 CCF 寫一個直播程式。

輸入格式

第一行有兩個整數 n, w。分別代表選手總數與獲獎率。
第二行有 n 個整數，依次代表逐一評出的選手成績。

輸出格式

只有一行，包含 n 個非負整數，依次代表選手成績逐一評出後，即時的獲獎分數線。相鄰兩個整數間用一個空格分隔。

樣例 #1

樣例輸入 #1

10 60
200 300 400 500 600 600 0 300 200 100

樣例輸出 #1

200 300 400 400 400 500 400 400 300 300

樣例 #2

樣例輸入 #2

10 30
100 100 600 100 100 100 100 100 100 100

樣例輸出 #2

100 100 600 600 600 600 100 100 100 100

提示

樣例 1 解釋

數據規模與約定

各測試點的 n 如下表：

對於所有測試點，每個選手的成績均為不超過 600 的非負整數，獲獎百分比 w 是一個正整數且 1 \le w \le 99。

分隔線

正文：

(為神馬題目那麼長)

OK，叕是一道簡單的題
由於題目給的範圍只有600，所以可以用：

桶排序！

桶排原理
所以：

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

完美！

本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/tong_pai_xu.html