Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Informatics/problems/priority_queue.md'

priority_queue 优先队列/堆

加入任意值
询问最大值
删除最大值

优先队列是唯一一个默认大的在前的内置函数
priority_queue is the only exception, which largest is the first

其他的比如
set
map
sort
lower_bound
都是小的在前
the first is the smallest

每个位置都 -= M 可以删去一段，和 < 0 说明 ans < M R = M
每个位置都 -= M 删去任意一段，和 >= 0 说明 ans >= M L = M

include

std::priority_queue

3个操作
加入一个数字 push
取出最大值 top
删去最大值 pop
（不能删去任意值）
如何支持删除

1. 直接用set
2. 每次取top之后，检查一下是不是最新版本
3. 用一个堆，记录删去了哪些元素，如果2个堆的堆顶相同，同时删去。

可以删除 相当于可以修改

priority_queue q;

priority_queue
可以是结构体
结构体需要重载 <
或者传比较函数

priority_queue 默认 大的数字在前 top 是最大的
这个和 其他STL都不相同

map set sort lower_bound ...
都是小的在前

priority_queue 支持的操作和 set/multiset 很相似
priority_queue 快一点，但是不支持删除任意元素
set/multiset 可以删除任意元素，set支持lower_bound，前驱，后继

lower_bound 查询set中 >=x 最小元素是什么？
upper_bound 查询set中 >x 最小元素是什么？

std::priority_queue<int, std::vector<int>, std::less<int> > q2;
等价于
std::priority_queue<int> q2;
大 的在前

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
小 的在前

堆是如何实现的
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P3378.cpp
如何用数组存储二叉树
根节点是0，x的左孩子是2x+1，右孩子是2x+2，父亲节点是(x-1)/2
根节点是1，x的左孩子是2x，右孩子是2x+1，父亲节点是x/2

堆的性质（以大根堆为例）
每个节点>=自己的两个孩子
最大值一定在根节点（堆顶）
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P3378.cpp

调整操作
up 向上调整
每次和自己的父亲节点比

down 向下调整
和自己较大的孩子比
（自己可能0个孩子，1个孩子，2个孩子）

1. 取最大值
   直接返回堆顶

2. 如何加入一个数字
   加在末尾，向上调整

3. 删除
   堆顶和最后一个交换，堆顶向下调整

4. 初始化
   输入一个数组，如何初始化成堆的样子。

显而易见的做法，一个一个加入
for (int i = 1; i <= n; i++)
{
up(i);
}
时间复杂度O(n log n)

另一个做法
for (int i = n; i >= 1; i--)
{
down(i);
}
O(n)

对于自己实现的堆，可以支持删除任意值
需要记录每个值的位置（所以在所有swap的时候，需要同时交换位置）

swap(a[需要删除的位置], a[n]);
n--;
up(需要删除的位置)
down(需要删除的位置)

P1090 合并果子
Huffman Code

k叉？（每次合并<=k堆）
合并一次减少k-1堆
如果(n-1)%(k-1)==0 和之前一样，贪心即可。
如果(n-1)%(k-1)>0 第一次合并最小的(n-1)%(k-1)+1堆，其他和之前一样。

P1334 瑞瑞的木板
和 合并果子 一样
需要long long

STL函数
make_heap
pop_heap
push_heap

P6033 合并果子 加强版
合并果子的 计数排序 队列优化

P1177 【模板】快速排序

https://www.luogu.com.cn/problem/P1177

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据，有 $N\leq 10^3$；

对于 $100\%$ 的数据，有 $N\leq 10^5$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[100020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

P1168 中位数

https://www.luogu.com.cn/problem/P1168

题目描述

给出一个长度为$N$的非负整数序列$A_i$，对于所有$1 ≤ k ≤ (N + 1) / 2$，输出$A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}$的中位数。即前$1,3,5,…$个数的中位数。

输入格式

第$1$行为一个正整数$N$，表示了序列长度。

第$2$行包含$N$个非负整数$A_i (A_i ≤ 10^9)$。

输出格式

共$(N + 1) / 2$行，第$i$行为$A_1, A_3, …, A_{2k - 1}$的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

提示

对于$20\%$的数据，$N ≤ 100$；

对于$40\%$的数据，$N ≤ 3000$；

对于$100\%$的数据，$N ≤ 100000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int, vector<int>, less<int> > q2;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (i == 1 || x > q1.top()) {
			q1.push(x);
		} else {
			q2.push(x);
		}
		if (q1.size() < q2.size()) {
			q1.push(q2.top());
			q2.pop();
		}
		if (q1.size() > q2.size() + 1) {
			q2.push(q1.top());
			q1.pop();
		}
		if (i % 2 == 1) {
			printf("%d\n", q1.top());
		}
	}
	return 0;
}

题解

#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > q1; 小根堆
priority_queue<int, vector<int>, less<int> > q2; 大根堆
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (i == 1 || x > q1.top()) {
			q1.push(x);
		} else {
			q2.push(x);
		}
		if (q1.size() < q2.size()) {
			q1.push(q2.top());
			q2.pop();
		}
		if (q1.size() > q2.size() + 1) {
			q2.push(q1.top());
			q1.pop();
		}
		// 时刻保证 q1.size() == q2.size() || q1.size() == q2.size() + 1
		// 时刻保证 q1.top() >= q2.top();
		if (i % 2 == 1) {
			printf("%d\n", q1.top());
		}
	}
	return 0;
}

P1801 黑匣子

https://www.luogu.com.cn/problem/P1801

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 $i$。最开始的时候 Black Box 是空的．而 $i=0$。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把 $x$ 元素放进 Black Box;

• GET：$i$ 加 $1$，然后输出 Black Box 中第 $i$ 小的数。

记住：第 $i$ 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 $i$ 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

序号	操作	$i$	数据库	输出
1	ADD(3)	$0$	$3$	/
2	GET	$1$	$3$	$3$
3	ADD(1)	$1$	$1,3$	/
4	GET	$2$	$1,3$	$3$
5	ADD(-4)	$2$	$-4,1,3$	/
6	ADD(2)	$2$	$-4,1,2,3$	/
7	ADD(8)	$2$	$-4,1,2,3,8$	/
8	ADD(-1000)	$2$	$-1000,-4,1,2,3,8$	/
9	GET	$3$	$-1000,-4,1,2,3,8$	$1$
10	GET	$4$	$-1000,-4,1,2,3,8$	$2$
11	ADD(2)	$4$	$-1000,-4,1,2,2,3,8$	/

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 $m$ 个，GET 命令共有 $n$ 个。现在用两个整数数组来表示命令串：

1. $a_1,a_2,\cdots,a_m$：一串将要被放进 Black Box 的元素。例如上面的例子中 $a=[3,1,-4,2,8,-1000,2]$。

2. $u_1,u_2,\cdots,u_n$：表示第 $u_i$ 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 $u=[1,2,6,6]$ 。输入数据不用判错。

输入格式

第一行两个整数 $m$ 和 $n$，表示元素的个数和 GET 命令的个数。

第二行共 $m$ 个整数，从左至右第 $i$ 个整数为 $a_i$，用空格隔开。

第三行共 $n$ 个整数，从左至右第 $i$ 个整数为 $u_i$，用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

样例 #1

样例输入 #1

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

样例输出 #1

3
3
1
2

提示

数据规模与约定

• 对于 $30\%$ 的数据，$1 \leq n,m \leq 10^{4}$。
• 对于 $50\%$ 的数据，$1 \leq n,m \leq 10^{5}$。
• 对于 $100\%$ 的数据，$1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$，保证 $u$ 序列单调不降。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, a[200020];
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int, vector<int>, less<int> > q2;
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0, j = 0; i < m; i++)
	{
		cin >> x;
		for (; j < x; j++)
		{
			q2.push(a[j]);
			if (q2.size() > i)
			{
				q1.push(q2.top());
				q2.pop();
			}
		}
		cout << q1.top() << endl;
		q2.push(q1.top());
		q1.pop();
	}
	return 0;
}

题解

和中位数类似的思路，2个堆

P1631 序列合并

https://www.luogu.com.cn/problem/P1631

题目描述

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到$N^2$个和，求这$N^2$个和中最小的N个。

输入格式

第一行一个正整数N；

第二行N个整数$A_i$, 满足$A_i\le A_{i+1}$且$A_i\le 10^9$;

第三行N个整数$B_i$, 满足$B_i\le B_{i+1}$且$B_i\le 10^9$.

【数据规模】

对于50%的数据中，满足1<=N<=1000；

对于100%的数据中，满足1<=N<=100000。

输出格式

输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

样例 #1

样例输入 #1

3
2 6 6
1 4 8

样例输出 #1

3 6 7

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100020];
int b[100020];
int p[100020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &b[i]);
		q.push(make_pair(-a[p[i]] - b[i], i));
	}
	for (int i = 0; i < n; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d", -u.first);
		if (i == n - 1) {
			printf("\n");
			break;
		} else {
			printf(" ");
		}
		p[u.second]++;
		q.push(make_pair(-a[p[u.second]] - b[u.second], u.second));
	}
	return 0;
}

题解

注意到a[i] + b[j] 如果ij>n 一定不会被选择
考虑有多少个位置满足 ij <= n
n / 1 + n / 2 + .. + n / n 约等于 n log n
在n log n个数字中求最小的n个

for (int i = 1; i <= n && i <= a.size(); i++)
{
	for (int j = 1; j * i <= n && j <= b.size(); j++)
	{
		re.push_back(a[i-1] + b[j-1]);
	}
}
sort(re.begin(), re.end());
re.resize(n);
return re;

P2085 最小函数值

https://www.luogu.com.cn/problem/P2085

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

样例 #1

样例输入 #1

3 10
4 5 3
3 4 5
1 7 1

样例输出 #1

9 12 12 19 25 29 31 44 45 54

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10,B_i\le100,C_i\le10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10020];
int b[10020];
int c[10020];
int p[10020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		int j = i;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	for (int i = 0; i < m; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d%c", -u.first, i == m - 1 ? '\n' : ' ');
		int j = u.second;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	return 0;
}

题解

Fi(x) < Fi(x+1)
一定先取x再取x+1

P3620 [APIO/CTSC 2007] 数据备份

https://www.luogu.com.cn/problem/P3620

题目描述

你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼(或总计 2K 个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说，这 2K 个办公楼一定是相异的)。

此外，电信公司需按网络电缆的长度(公里数)收费。因而，你需要选择这 K对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和(总距离)尽可能小。

下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。

上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km―1km = 2km，第 2 条电缆的长度是 6km―4km = 2 km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。

输入格式

输入文件的第一行包含整数 n 和 k，其中 n(1≤n≤100 000)表示办公楼的数目，k(1≤k≤n/2)表示可利用的网络电缆的数目。

接下来的 n 行每行仅包含一个整数(0≤s≤1000 000 000), 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出格式

输出文件应当由一个正整数组成，给出将 2K 个相异的办公楼连成 K 对所需的网络电缆的最小总长度。

样例 #1

样例输入 #1

5 2 
1 
3 
4 
6 
12 

样例输出 #1

4

提示

30%的输入数据满足 n≤20。

60%的输入数据满足 n≤10 000

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[100020];
int nxt[100020];
int pre[100020];
set<pair<int, int> > s;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		pre[i + 1] = i;
		nxt[i] = i + 1;
	}
	for (int i = n - 1; i > 0; i--) {
		a[i] -= a[i - 1];
		s.insert(make_pair(a[i], i));
	}
	a[0] = 1e9;
	a[n] = 1e9;
	int z = 0;
	for (int i = 0; i < k; i++) {
		int x = s.begin()->second;
		s.erase(s.begin());
		z += a[x];
		s.erase(make_pair(a[pre[x]], pre[x]));
		s.erase(make_pair(a[nxt[x]], nxt[x]));
		a[x] = a[pre[x]] + a[nxt[x]] - a[x];
		s.insert(make_pair(a[x], x));
		pre[x] = pre[pre[x]];
		nxt[x] = nxt[nxt[x]];
		nxt[pre[x]] = x;
		pre[nxt[x]] = x;
	}
	printf("%lld\n", z);
	return 0;
}

题解

2 1 2 6

1000000000 1 2 3 4

a b c 选择中间的b
变成1个数字
a+c-b

51nod 1380 夹克老爷的逢三抽一

P1878 舞蹈课

https://www.luogu.com.cn/problem/P1878

题目描述

有 $n$ 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD）。舞蹈技术相差最小即是 $a_i$ 的绝对值最小。

任务是模拟以上过程，确定跳舞的配对及顺序。

输入格式

第一行一个正整数 $n$ 表示队伍中的人数。

第二行包含 $n$ 个字符 B 或者 G，B 代表男，G 代表女。

第三行为 $n$ 个整数 $a_i$。所有信息按照从左到右的顺序给出。

输出格式

第一行一个整数表示出列的总对数 $k$。

接下来 $k$ 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 $1$ 至 $n$ 编号）。请先输出较小的整数，再输出较大的整数。

样例 #1

样例输入 #1

4
BGBG
4 2 4 3

样例输出 #1

2
3 4
1 2

提示

对于 $50\%$ 的数据，$1\leq n\leq 200$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\le a_i\le 10^7$。

参考代码

题解

P5120 [USACO18DEC]Convention II S

https://www.luogu.com.cn/problem/P5120

题目描述

虽然在接机上耽误了挺长时间，Farmer John 为吃草爱好牛们举行的大会至今为止都非常顺利。大会吸引了世界各地的奶牛。

然而大会的重头戏看起来却给 Farmer John 带来了一些新的安排上的困扰。他的农场上的一块非常小的牧草地出产一种据某些识货的奶牛说是世界上最美味的品种的草。因此，所有参会的 $N$ 头奶牛（$1\le N\le 10^5$）都想要品尝一下这种草。由于这块牧草地小到仅能容纳一头奶牛，这很有可能会导致排起长龙。

Farmer John 知道每头奶牛i计划到达这块特殊的牧草地的时间 $a_i$，以及当轮到她时，她计划品尝这种草花费的时间 $t_i$。当奶牛 $i$ 开始吃草时，她会在离开前花费全部 $t_i$ 的时间，此时其他到达的奶牛需要排队等候。如果这块牧草地空出来的时候多头奶牛同时在等候，那么资历最深的奶牛将会是下一头品尝鲜草的奶牛。在这里，恰好在另一头奶牛吃完草离开时到达的奶牛被认为是“在等待的”。类似地，如果当没有奶牛在吃草的时候有多头奶牛同时到达，那么资历最深的奶牛是下一头吃草的奶牛。

请帮助 FJ 计算所有奶牛中在队伍里等待的时间（$a_i$ 到这头奶牛开始吃草之间的时间）的最大值。

输入格式

输入的第一行包含 $N$。以下 $N$ 行按资历顺序给出了 $N$ 头奶牛的信息（资历最深的奶牛排在最前面）。每行包含一头奶牛的 $a_i$ 和 $t_i$。所有的 $t_i$ 为不超过 $10^4$ 的正整数，所有 $a_i$ 为不超过 $10^9$ 的正整数。

输出格式

输出所有奶牛中的最长等待时间。

样例 #1

样例输入 #1

5
25 3
105 30
20 50
10 17
100 10

样例输出 #1

10

提示

在这个例子中，我们有 $5$ 头奶牛（按输入中的顺序编号为 $1\dots 5$）。奶牛 $4$ 最先到达（时间 $10$），在她吃完之前（时间 $27$）奶牛 $1$ 和奶牛 $3$ 都到达了。由于奶牛 $1$ 拥有较深的资历，所以她先吃，从她到达开始共计等待了 $2$ 个单位时间。她在时间 $30$ 结束吃草，随后奶牛 $3$ 开始吃草，从她到达开始共计等待了 $10$ 单位时间。在一段没有奶牛吃草的时间过后，奶牛 $5$ 到达，在她正在吃草的时间里奶牛 $2$ 也到达了，在 $5$ 个单位时间之后能够吃到草。相比到达时间等待最久的奶牛是奶牛 $3$。

参考代码

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int n;
pair<pair<int, int>, int> a[100020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].X.X, &a[i].Y);
		a[i].X.Y = i;
	}
	sort(a, a + n);
	int z = 0, i = 0, t = 0;
	set<pair<pair<int, int>, int> > s;
	while (i < n || s.size()) {
		while (i < n && a[i].X.X <= t) {
			swap(a[i].X.X, a[i].X.Y);
			s.insert(a[i++]);
		}
		if (s.size() == 0) {
			t = a[i].X.X;
			continue;
		}
		z = max(z, t - s.begin()->X.Y);
		t += s.begin()->Y;
		s.erase(s.begin());
	}
	printf("%d\n", z);
	return 0;
}

题解

P1382 楼房

https://www.luogu.com.cn/problem/P1382

题目描述

地平线（$x$ 轴）上有 $n$ 个楼房，每个楼房可以表示为一个矩形。

用三个整数 $h_i,l_i,r_i$ 来表示第 $i$ 个矩形：矩形左下角为 $(l_i,0)$，右上角为 $(r_i,h_i)$。

地平线高度为 $0$。在轮廓线长度最小的前提下，从左到右输出轮廓线。

输入格式

第一行一个整数 $n$，表示矩形个数。

以下 $n$ 行，每行 $3$ 个整数 $h_i,l_i,r_i$ 表示第 $i$ 个矩形。

输出格式

第一行一个整数 $m$，表示节点个数。

以下 $m$ 行，每行一个坐标表示轮廓线上的节点。

要求从左到右遍历轮廓线并顺序输出节点。

注：第一个和最后一个节点的 $y$ 坐标必然为 $0$。

样例 #1

样例输入 #1

2
3 0 2
4 1 3

样例输出 #1

6
0 0
0 3
1 3
1 4
3 4
3 0

样例 #2

样例输入 #2

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

样例输出 #2

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

提示

样例二如图：

数据范围:

对于 $30\%$ 的数据，$n\le100$。

对于另外 $30\%$ 的数据，$1\le h_i,l_i,r_i\le 1000$。

对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le h_i\le 10^9$，$-10^9\le l_i<r_i\le10^9$。

参考代码

题解

扫描线 set

P2707 Facer帮父亲

https://www.luogu.com.cn/problem/P2707

题目背景

Facer可是一个孝顺的孩纸呦

题目描述

Facer的父亲是一名经理，现在总是垂头丧气的。

Facer问父亲，怎么啦？父亲说，公司出了点问题啊。

公司管理着N个风景点，每个风景点都有不少人来参观。

可是现在！人民投诉票价太高了，他不得不调整票价

具体来说，第i个景点如果票价是x，来的人数就是max( (ai - bi * x),0 )[收益自己算好伐]

你需要分配每个景点的门票，使得每个景点门票总和不超过k，且最大化收益

求最大的收益

输入格式

第一行N , k

接下来N行，每行ai,bi

输出格式

一行，最大的收益

样例 #1

样例输入 #1

2 4
50 2
40 1

样例输出 #1

171

提示

样例解释：

景点1票价3，景点2票价1

景点1人数：50 - 3*2 = 44 票价 :3 收益:132

景点2人数 : 40 - 1*1 = 39 票价 : 1 收益:39

总收益171 最大

10%  n <= 5 , k <= 5
30%  n <= 100,k <= 100
60%  n <= 2000,k <= 2000
100%n <= 100000,k <= 100000
1 <= ai , bi <= 100000
鸣谢 zhouyonglong 提供解法

参考代码

题解

P2085 最小函数值

https://www.luogu.com.cn/problem/P2085

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

样例 #1

样例输入 #1

3 10
4 5 3
3 4 5
1 7 1

样例输出 #1

9 12 12 19 25 29 31 44 45 54

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10,B_i\le100,C_i\le10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10020];
int b[10020];
int c[10020];
int p[10020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		int j = i;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	for (int i = 0; i < m; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d%c", -u.first, i == m - 1 ? '\n' : ' ');
		int j = u.second;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	return 0;
}

题解

Fi(x) < Fi(x+1)
一定先取x再取x+1

P3045 [USACO12FEB]Cow Coupons G

https://www.luogu.com.cn/problem/P3045

题目描述

Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

FJ准备买一些新奶牛，市场上有N头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^{9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=10}14)的钱最多可以买多少奶牛？

输入格式

* Line 1: Three space-separated integers: N, K, and M.

* Lines 2..N+1: Line i+1 contains two integers: P_i and C_i.

输出格式

* Line 1: A single integer, the maximum number of cows FJ can afford.

样例 #1

样例输入 #1

4 1 7 
3 2 
2 2 
8 1 
4 3 

样例输出 #1

3 

提示

FJ has 4 cows, 1 coupon, and a budget of 7.

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
long long m, s;
int c[100020];
int p[100020];
pair<int, int> a[100020];
pair<int, int> b[100020];
bool v[100020];
int main() {
	cin >> n >> k >> m;
	for (int i = 0; i < n; i++) {
		cin >> p[i] >> c[i];
		a[i].first = c[i];
		b[i].first = p[i];
		a[i].second = b[i].second = i;
	}
	sort(a, a + n);
	sort(b, b + n);
	priority_queue<int, vector<int>, greater<int> > q;
	q.push(1000000000);
	for (int i = 0; i < k; i++) {
		q.push(0);
	}
	int pa = 0;
	int pb = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		while (v[a[pa].second]) {
			pa++;
		}
		while (v[b[pb].second]) {
			pb++;
		}
		if (a[pa].first + q.top() < b[pb].first) {
			v[a[pa].second] = true;
			s += a[pa].first + q.top();
			q.pop();
			q.push(p[a[pa].second] - a[pa].first);
			assert(c[a[pa].second] == a[pa].first);
		} else {
			v[b[pb].second] = true;
			s += b[pb].first;
		}
		if (s <= m) {
			ans = max(ans, i + 1);
		}
	}
	cout << ans << endl;
}

题解

优先队列 可以优化 dijkstra

Java PriorityQueue

P2107 小Z的AK计划

https://www.luogu.com.cn/problem/P2107

题目描述

在小Z的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小Z刚刷完CodeChef，准备出来逛逛。

机房一条街有 n 个机房，第 i 个机房的坐标为 xi ，小Z的家坐标为 0。小Z在街上移动的速度为1，即从 x1 到 x2 所耗费的时间为 |x1 - x2|。
每个机房的学生数量不同，ACM 题目水平也良莠不齐。小Z到达第 i 个机房后，可以花 ti 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。

小Z现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

输入格式

第一行包含两个整数 n，m。

接下来 n 行，每行包含两个整数 xi，ti 。

输出格式

第一行包含一个整数，表示小Z最多能 AK 的机房数量。

样例 #1

样例输入 #1

2 10
1 100
5 5

样例输出 #1

1

提示

【数据规模】

对于 30% 的数据，n ≤ 20。

对于 60% 的数据，n ≤ 1000。

对于 100% 的数据，1 ≤ n ≤ 10^5，0 ≤ m，xi ≤ 10^18，0 ≤ ti ≤ 10^9。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, z;
ll m, s;
pair<ll, ll> a[100020];
priority_queue<ll> q;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (a[i].first > m) {
			break;
		}
		q.push(a[i].second);
		s += a[i].second;
		while (s + a[i].first > m) {
			s -= q.top();
			q.pop();
		}
		z = max(z, (int)q.size());
	}
	cout << z << endl;
}

题解

带反悔的贪心
一定是从原点向右走到某个位置，在路过的任务中选最小的若干个来做。

P2949 [USACO09OPEN]Work Scheduling G

https://www.luogu.com.cn/problem/P2949

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

样例 #1

样例输入 #1

3 
2 10 
1 5 
1 7 

样例输出 #1

17 

提示

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int> > q;
pair<int, int> a[100020];
long long z;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += a[i].second;
		q.push(a[i].second);
		if (q.size() > a[i].first)
		{
			z -= q.top();
			q.pop();
		}
	}
	printf("%lld\n", z);
	return 0;
}

题解

带反悔的贪心

假设决定了做哪些任务，一定是按照截止时间排序来做。
对于任意一个时间x，
截止时间<=x的任务 消耗的总时间 必须<=x
截止时间<=x的任务 个数 必须<=x

扫描所有任务，每次直接选择，如果当前选择的任务个数 > 截止时间，在所有已经选择的任务中，
扔掉获利最小的（扔掉获利最小的任务时，不考虑截止时间）

假设每个任务消耗的时间不相同
可以用背包解决
先排序
每个任务更新时，只更新到自己的截止时间

背包时，不同物品的放置顺序是有关系的
先考虑假设要选择一个集合
按哪种顺序一定可以放置成功
先把这些物品按照这个顺序排序

CF101623I

https://codeforces.com/gym/101623/attachments
https://codeforces.com/gym/101623/problem/I