自动搬运

查看原文

来自洛谷，原作者为

	AzusagawaKaede QAQ

搬运于2025-08-24 22:26:22，当前版本为作者最后更新于2020-11-08 00:24:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7072 直播获奖 题解

$update:$ 优化了代码的风格

蒟蒻的第一篇题解 求过

此题动态维护第K大数，显然对顶堆

---

先来看几种错误解法：

1. 每读入一个就sort排序一次（$50pts$）

这种解法最好想，相应的分也就最少

代码如下

scanf("%d%d", &n, &w);
for (int p = 1; p <= n; p++)
{
	now=max(1,p*w/100);
	scanf("%d", &a[p]);
	sort(a+1, a+p+1, greater<int>());
	printf("%d ", a[now]); 
}
return 0;

结果如下

2. 整体做一次插入排序，边读边做插入排序边输出（$85pts$）

复杂度$O(n^2)$,神奇地过了n=10^4的数据

代码如下

scanf("%d%d", &n, &w);
a[0]=0x7fffffff;
for (int p = 1; p <= n; p++)
{
	now=max(1,p*w/100);
	scanf("%d", &num);
	for (int i = p; i >= 0; i--)
	{
		if (num < a[i])
		{
			a[i+1]=num;
			break;
		}
		else
		{
			a[i+1]=a[i];
		}
	} 
	printf("%d ", a[now]); 
}

结果如下

---

接下来，我们来了解对顶堆

1.什么是对顶堆？

通俗的说，对顶堆是一种简单好用的动态维护单调区间第k大数或第k小数的数据结构 （好像也不怎么通俗啊）, 由一个大顶堆和一个小顶堆构成

先看图（由于题意降序排列，小顶堆在上， 大顶堆在下。反之亦然 ）：

不言而喻，一目了然

---

2. 基本操作

1. 插入元素

void push(int num)
{
	if (num >= ma_hp.top())
   		mi_hp.push(num);
	else ma_hp.push(num);
	qwq();//调整小顶堆元素个数
}

2. 在两个堆之间交换元素:

大->小（下->上）:

mi_hp.push(ma_hp.top());
ma_hp.pop();

小->大（上->下）:

ma_hp.push(mi_hp.top());
mi_hp.pop();

3. 查询

mi_hp.top();

注意：插入元素时应注意整个序列的单调性，判断应插入上面还是下面 于是题目就变成一个动态维护序列第p*w%大数的题目啦~

---

3. 代码

递上一份蒟蒻写的蒟蒻代码

$code:$

#include <bits/stdc++.h>

using namespace std;

priority_queue<int> ma_hp;//大顶堆 
priority_queue<int, vector<int>, greater<int> > mi_hp;//小顶堆 

int n, w, now, num;

void qwq()//调整获奖人数（小顶堆元素个数）
{
	if (mi_hp.size()<now)
	{
		mi_hp.push(ma_hp.top());
		ma_hp.pop();
	} 
	if (mi_hp.size() > now)
	{
		ma_hp.push(mi_hp.top());
		mi_hp.pop();
	}
	
} 

void push(int num)
{
	if (num >= ma_hp.top()) mi_hp.push(num);
		else ma_hp.push(num);
	qwq();
}

int main()
{
	scanf("%d%d", &n, &w);
	ma_hp.push(0);//避免边界判断 
	for (int p = 1; p <= n; p++)
	{
		now=max(1,p*w/100);;//实时获奖人数 
		scanf("%d", &num);
		push(num);
		printf("%d ", mi_hp.top()); 
	}
	return 0;
}

result：

PS：由于数据范围较小，官方正解应该是桶排序。但是对顶堆可以应对数据更大的题目，并且代码也非常短，是一种非常好用的数据结构呢。

对顶堆练手题目：P3871

点个赞再走吧

谢谢