鏈接：https://ac.nowcoder.com/acm/contest/8848/B
來源：牛客網
題目描述
題目資料為牛客制作的民間資料，可以提交測驗，結果僅供參考，不代表官方成績，最終成績以官方發布的最終成績為準，
NOI2130 即將舉行，為了增加觀賞性，CCF 決定逐一評出每個選手的成績，并直播即時的獲獎分數線，本次競賽的獲獎率為 w%，即當前排名前 w%
的選手的最低成績就是即時的分數線，
更具體地，若當前已評出了 𝑝 個選手的成績，則當前計劃獲獎人數為 max(1,?p×w%?)，其中 𝑤 是獲獎百分比，?𝑥? 表示對 𝑥x 向下取整， max(𝑥, 𝑦) 表示 𝑥 和 𝑦 中較大的數，如有選手成績相同，則所有成績并列的選手都能獲獎，因此實際獲獎人數可能比計劃中多，
作為評測組的技術人員，請你幫 CCF 寫一個直播程式，
輸入描述:
第 11 行兩個正整數 𝑛, 𝑤，分別代表選手總數與獲獎率，
第 22 行有 𝑛 個非負整數，依次代表逐一評出的選手成績，
輸出描述:
只有一行，包含 𝑛 個非負整數，依次代表選手成績逐一評出后，即時的獲獎分數線，相鄰兩個整數間用一個空格分隔，
示例1
輸入
10 60
200 300 400 500 600 600 0 300 200 100
輸出
200 300 400 400 400 500 400 400 300 300
題目大意
將前i個數排序，輸出第max(1,?i×w%?)大的數，
思路
用兩個優先佇列維護前i個的降序排序，用一個升序優先佇列q和一個降序優先佇列p分別存每次排序的前max(1,?i×w%?)個和第max(1,?i×w%?)之后的
以樣例1為例
每次插入一個數判斷這個數可以放在是在p中還是q中，如果可以放在p中，就將最小的數移到q中，如果在q中，就把q中最大的數移動到p中
AC代碼（附良心注釋）
#include<bits/stdc++.h>
using namespace std;
int a[100004];
priority_queue<int,vector<int>,greater<int> >q;//升序
priority_queue<int>p;//默認降序
int sca()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
w=ch=='-'?-1:w,ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
int b,n,num;
n=sca();b=sca();
for(int i=1; i<=n; i++)
{
a[i]=sca();num=max(1,i*b/100);
if(q.size()<num)//q是升序
{
if(p.empty())
q.push(a[i]);
else
{
if(p.top()<a[i])
q.push(a[i]);
else
q.push(p.top()),p.pop(),p.push(a[i]);//從p中補一個最大的到q佇列籌齊q個
}
}
else
{
while(q.top()<a[i]&&(int)q.size()>=num)//在p佇列中有num個的前提下洗掉比a[i]小的
p.push(q.top()),q.pop();//將q的最小的元素加入到p優先佇列中
if(q.size()<num)//說明a[i]的大小在q中
q.push(a[i]);
else //a[i]比為num的q的最小值還小
p.push(a[i]);//q中已有num個，將a[i]加入p佇列
}
printf("%d%c",q.top(),i==n?'\n':' ');
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/209411.html
標籤：其他
上一篇：鄭州輕工業大學新生周賽2題解
下一篇：利用Java模擬石頭剪刀布游戲