标签：大根堆 tsk int queue 扫描线小根堆应用

前言

本文针对 CSP-S2/NOIP 复习，重点在在哪用、怎么写，底层原理和实现不是重点。

堆的概念和应用情景

堆是一种可以在 \(O(\log n)\) 的时间内维护一个最值的数据结构，维护最大值的称为大根堆，维护最小值的称为小根堆。
堆的应用只有一个，就是求最值，但求什么最值、求出最值后怎么用，需要根据题目具体分析。
- 使用对顶堆可以维护第 \(k\%\) 位数（见例题）
- 反悔贪心一般需要维护所做的最劣决策，一般也会用到若干个堆（见例题）

堆的实现（`priority_queue`）

现在比赛可以用 stl 了，所以就不复习怎么手写堆了，用 priority_queue 就行了。

存已有的数据类型

priority_queue <int, vector<int>, greater<int> > q;

先声明 priority_queue
参数要么只写一个数据类型（像 int、long long ……），要么就三件套，数据类型、vector、比较方式
- 比较方式有两种，greater<数据类型> 和 less<数据类型>，分别表示当数字大/小时下沉，也就对应了小根堆和大根堆。
- 需要特别注意：greater 是小根堆！greater 是小根堆！大于表示大数字下沉而小数字在堆顶！
- 如果只写数据类型而不声明比较方式，默认为大根堆

存 struct

存 struct 需要重载运算符。
- 重载的一定是小于号，因为 priority_queue 默认大根堆，调用小于号
- 重载部分，< 对应大根堆，> 对应小根堆。
重载完之后只需要写数据类型就够了，不用再声明比较方式了。

struct node {
	// 这里写一些结构体中的变量
	int x;
	// 这里是重载部分
	const bool <(const node& x) const
	{
		return x < b.x;  // 大根堆
		// return x > b.x; 就是小根堆  
	}
};

priority_queue <node> q;

堆的删除

在堆中，除了堆顶之外，具体元素的位置是不清楚的，遍历删除耗时太久，可以用懒删除。（具体见例题 P2061）

例题

题目	备注
P7072 [CSP-J2020] 直播获奖	对顶堆，k%位数
P2949 [USACO09OPEN] Work Scheduling G	反悔贪心
P2061 [USACO07OPEN] City Horizon S	扫描线，堆的删除
iai433 分数排序	普通的堆，但比较难想

P7072 [CSP-J2020] 直播获奖

\(k\%\) 位数问题，是堆的一个经典应用。
解法是对顶堆：开一个大根堆 q 和一个小根堆 p，大根堆存小数字，小根堆存大数字，并且保证总数为奇数时，小根堆的大小恰好为 \(p\times w\%\)。
每当考虑一个新的数字 \(a\) 时，做两步：

因为大根堆要存小数字，所以先拿 \(a\) 和 q.top() 进行比较，来决定加入哪个堆中。
再调整小根堆的大小，小根堆多就把多出来的数字丢到大根堆，少就从大根堆里弹出堆顶补充。
题目中所求的答案即为小根堆堆顶。

比如对于这组数据：5, 6, 1, 2, 7, 4, 1、\(w=50\)。
假设我们已经知道了前五个数的 \(50\%\) 位数是 5。
则现在大根堆中的数据：2, 1，小根堆中的数据为 5, 6, 7。

处理接下来一个数字 4，在这里，因为 4 比大根堆堆顶 2 大，所以加入小根堆。
现在小根堆中有 4 个数字：4, 5, 6, 7，而 \(p\times w\%=3\)，所以把小根堆堆顶 4 弹出，放到大根堆
现在大根堆中的数据：4, 2, 1，小根堆中的数据为 5, 6, 7，输出答案 5。

再处理接下来一个数字 1，比大根堆堆顶 4 小，所以加入大根堆
现在大根堆中的数据：4, 2, 1, 1，小根堆中的数据为 5, 6, 7，\(p\times w\%=4\)。
调整大小，把大根堆堆顶 4 弹出放入小根堆。
现在大根堆中的数据：2, 1, 1，小根堆中的数据为 4, 5, 6, 7，输出答案 4。

实现方面，只需要用两个 priority_queue 即可。

AC 代码

AC 代码提交记录

#include <bits/stdc++.h>

using namespace std;

int n, w;
priority_queue <int> q;
priority_queue <int, vector<int>, greater<int>> p;

int main()
{
	cin >> n >> w;
	for (int i = 1; i <= n; ++i) {
		int x, k=max(1, i*w/100);
		cin >> x;
		if (q.empty() || x > q.top()) {
			p.push(x);
		} else {
			q.push(x);
		}
		while (!p.empty() && p.size() > k) { q.push(p.top()); p.pop(); }
		while (!p.empty() && p.size() < k) { p.push(q.top()); q.pop(); }
		cout << p.top() << " ";
	}
	return 0;
}

P2949 [USACO09OPEN] Work Scheduling G

可能第一眼看到要求最值会联想到 dp，但很快就会发现，dp 的状态很难表示，而且有后效性，维度太多复杂度又吃不住，考虑贪心。
这里有两种贪心的方法。

解法 1：反向扫描，纯粹的贪心

把问题变一下：从某个时刻 \(D_i\) 开始能够做一项任务，完成会有 \(P_i\) 的收益。
这样贪心思路就很明确了，每次都挑手上能做的、收益最高的那一个任务即可，不用考虑需不需要给后面任务留时间的问题，因为后面的任务还没有开始。
当前手上收益最高的任务，可以用堆维护。
AC 代码提交记录

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN=1e5+5;
int n;
ll ans;

struct node {
	ll d, p;
} tsk[MAXN];

priority_queue <ll, vector<ll>, less<ll> > q;

int main()
{
//	freopen("P2949_3.in", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> tsk[i].d >> tsk[i].p;
	}
	tsk[++n] = {0, 0};
	sort(tsk+1, tsk+n+1, [](node a, node b){return (a.d>b.d)||(a.d==b.d&&a.p>b.p);});
	q.push(tsk[1].p);
	ll j = tsk[1].d;
	for (int i = 2; i <= n; ++i) {
		j = min(j, tsk[i-1].d);
		while ( (!q.empty()) && (j > tsk[i].d) ) {
			ans+=q.top(); q.pop(); --j;
		}
		q.push(tsk[i].p);
	}
	cout << ans << endl;
}

解法 2：正向扫描，反悔贪心

正向扫描需要解决的最大问题就是：需不需要给后面任务留时间。
比如对于这组数据：

最大收益是 \(5+7+4=16\)，在这里就是把 \(i=2\) 的那一个任务放弃，把时间留给 \(i=4\) 的那一个任务了。

我们可以利用反悔贪心的思想来考虑这个问题。
也就是说，讲任务按照时间从前往后排序之后，每次碰到一个任务，就先接手开干。然后考虑：

如果新遇到的任务和已有的任务时间不冲突，那么就接受。
如果冲突了，那么，和手上收益最低的那个任务比较收益谁更大，考虑用新任务替换是不是赚，并且做收益的增量更新。

这里需要维护已有任务的最低收益，可以用堆。

AC 代码提交记录

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN=1e5+5;
int n;
long long ans;

struct node {
	ll d, p;
} tsk[MAXN];

priority_queue <ll, vector<ll>, greater<ll>> q;

int main()
{
//	freopen("P2949_3.in", "r", stdin);
	cin >> n;
	for (int i = 1; i <= n; ++i) { cin >> tsk[i].d >> tsk[i].p; }
	sort(tsk+1, tsk+n+1, [](node a, node b){return a.d<b.d;});
	for (int i = 1; i <= n; ++i) {
		if (tsk[i].d > q.size()) {
			ans += tsk[i].p;
			q.push(tsk[i].p);
		} else if (tsk[i].p > q.top()) {
			ans += tsk[i].p-q.top();
			q.pop();
			q.push(tsk[i].p);
		}
	}
	cout << ans << endl; return 0;
}

P2061 [USACO07OPEN] City Horizon S

矩形面积并，一眼【扫描线】。
从左往右，在有建筑开始或结束的地方，放一条假想的、垂直于地平线的【扫描线】，对合并完之后的那个奇形怪状的图形做切割。

这样一来，每次切割出来的部分是一个矩形。面积可以拿相邻两条扫描线的距离差 \(\Delta x\)，乘上这段里面的高度最大值 \(h_{max}\)。
答案是这 \(2n\) 条扫描线切割出来的面积之和，即 \(S=\sum(\Delta x\times h_{max})\)。

因为扫描线是人为定下来的，\(\Delta x\) 很好求，难点在于如何维护 \(h_{max}\)。
二维平面上的扫描线需要用到线段树，但在这里，因为题干中有地平线的存在，只需要拿一个堆即可。
假设我们已经维护出了前 \(i\) 条扫描线 \(bd_i\)，对于第 \(i+1\) 条扫描线 \(bd_{i+1}\)：

两条扫描线之间的距离差为 \(\Delta x=bd_{i+1}.x-bd_i.x\)，从堆中取出 \(h_{max}\)，将 \(\Delta x\times h_{max}\) 计入答案。
如果这条扫描线标记了某一幢建筑的【起点】，那么将这幢建筑的高度加入堆中。
如果这条扫描线标记了某一幢建筑的【终点】，那么执行删除操作。

接下来介绍堆的删除操作：【懒删除】。
因为在堆中，我们只能很快知道堆顶的元素，对于具体元素的位置需要遍历整个堆，时间吃不住。
但是，我们可以发现，如果被删去的元素不在堆顶，那么将不会从堆中取出被删去的元素，进而也就不会对答案产生影响。
所以我们可以用 flag 数组，或者 cnt 数组，或者再开一个堆，记下所有要删除的元素。
每次从堆中取出元素时，检查它是否被删除，然后才真正执行删除操作。

当然，在这题中，可以比较当前扫描线的位置，和取出的高度所代表的这幢楼的终点的位置，也可以判断取出的 \(h_{max}\) 是否合法。

AC 代码

AC 代码提交记录

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN=4e4+5;
int n;
ll ans;

struct node {
	ll x, h;
	bool st;
} bd[MAXN<<1];

priority_queue <ll> q, del_q;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		long long a, b, h; cin >> a >> b >> h;
		bd[2*i-1] = { a, h, 1 };
		bd[2*i]   = { b, h, 0 };
	}
	sort(bd+1, bd+2*n+1, [](node a, node b){return a.x<b.x;});
	for (int i = 1; i <= 2*n; ++i) {
		while ( (!q.empty()) && (!del_q.empty()) && (q.top() == del_q.top())) { q.pop(); del_q.pop(); }
		if (!q.empty()) { ans += q.top() * (bd[i].x-bd[i-1].x); }
		if (bd[i].st) { q.push(bd[i].h); }
		else            { del_q.push(bd[i].h); }
	}
	cout << ans << endl;
}

iai433 分数排序

\(\displaystyle\frac ab\) 是最简真分数，等价于 \(a,b\) 互质，等价于 \(\gcd(a,b)=1\)。
把所有分数都罗列出来，复杂度是平方级别的，显然吃不住，只能拿 60 分，所以只能从小到大一个一个看。

如果分母相同，分子越小，分数越小。
如果分子相同，分母越大，分数越小。
如果分子分母都不相同，就没办法快速比较了。

所以这里可以用堆维护最小的分数，相同分母的分数，只要选最小的那个加入堆即可。
初始时，堆中有 \(n-1\) 个元素，分别为 \(\displaystyle\frac12, \frac13, \cdots, \frac1n\)。
每次取出最小的那一个 \(\displaystyle\frac ab\)，然后考虑下一个以 \(b\) 为分母的分数 \(\displaystyle\frac{a+1}{b}\)，如果是最简真分数就入堆，不合法就再枚举下一个。

AC 代码

AC代码提交记录

#include <bits/stdc++.h>

using namespace std;

const int MAXK=2e5+5;
int n, k, cnt;

struct node {
	int a, b;
	double a_b;
	bool operator <(const node &x) const
	{
		return a_b > x.a_b;
	}
} num;

priority_queue <node> q;

int main()
{
	cin >> n >> k;
	for (int i = 2; i <= n; ++i) { q.push({1, i, double(1)/i}); }
	node c;
	for (int i = 1; i <= k; ++i) {
		c=q.top(); q.pop();
		int a = c.a + 1;
		while ( (a < c.b) && (__gcd(a,c.b)!=1) ) { ++a; }
		q.push( {a, c.b, double(a)/c.b} );
	}
	cout << c.a << "/" << c.b << endl; return 0;
}

标签：大根堆,tsk,int,queue,扫描线,小根堆,应用
From： https://www.cnblogs.com/LittleDrinks/p/17737926.html

堆的应用

前言

堆的概念和应用情景

堆的实现（`priority_queue`）

存已有的数据类型

存 struct

堆的删除

例题

P7072 [CSP-J2020] 直播获奖

AC 代码

P2949 [USACO09OPEN] Work Scheduling G

解法 1：反向扫描，纯粹的贪心

解法 2：正向扫描，反悔贪心

P2061 [USACO07OPEN] City Horizon S

AC 代码

iai433 分数排序

AC 代码

相关文章

赞助商

阅读排行

堆的应用

前言

堆的概念和应用情景

堆的实现（priority_queue）

存已有的数据类型

存 struct

堆的删除

例题

P7072 [CSP-J2020] 直播获奖

AC 代码

P2949 [USACO09OPEN] Work Scheduling G

解法 1：反向扫描，纯粹的贪心

解法 2：正向扫描，反悔贪心

P2061 [USACO07OPEN] City Horizon S

AC 代码

iai433 分数排序

AC 代码

相关文章

赞助商

阅读排行

堆的实现（`priority_queue`）