A16 对顶堆 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P7072 ↗

题目描述

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$ ，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p \times w \%\rfloor)$ ，其中 $w$ 是获奖百分比， $\lfloor x \rfloor$ 表示对 $x$ 向下取整， $\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

输入格式

第一行有两个整数 $n, w$ 。分别代表选手总数与获奖率。
第二行有 $n$ 个整数，依次代表逐一评出的选手成绩。

输出格式

只有一行，包含 $n$ 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

输入输出样例

输入 #1

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

plaintext

输出 #1

200 300 400 400 400 500 400 400 300 300

plaintext

输入 #2

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

plaintext

输出 #2

100 100 600 600 600 600 100 100 100 100

plaintext

算法解析#

Python代码实现#


import heapq
a = [] # 大根堆
b = [] # 小根堆
n, w = map(int, input().split())
lis = list(map(int, input().split()))
for i in range(n):
    x = lis[i]
    k = max(1, int((i + 1) * w / 100))
    if len(b) == 0 or x >= b[0]:
        heapq.heappush(b, x)
    else:
        heapq.heappush(a, -x)
    while len(b) > k:
        heapq.heappush(a, -heapq.heappop(b))
    while len(b) < k:
        heapq.heappush(b, -heapq.heappop(a))
    print(b[0], end=" ")

python

C++代码实现#

#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int main(){
  int n,w; scanf("%d%d",&n,&w); //选手总数,获奖率
  priority_queue<int> a; //大根堆
  priority_queue<int,vector<int>,greater<int> > b;

  for(int i=1; i<=n; i++){
    int x; scanf("%d",&x);
    if(b.empty()||x>=b.top()) b.push(x); //插入
    else a.push(x);

    int k=max(1,i*w/100); //第k大
    while(b.size()>k) a.push(b.top()), b.pop(); //调整
    while(b.size()<k) b.push(a.top()), a.pop();
    printf("%d ", b.top()); //取值
  }
}