2020CSP-J普及组复赛(民间数据)直播获奖(live)题解

2020/11/10 10:20
阅读数 3.1K

链接: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;
}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部