贪心

简单介绍

贪心并不具体指某一个算法，而是指一种思路，即只考虑当前一步的最优解，不考虑之后。

可以理解为是最简单的动态规划。

排序

一类题目是需要决定一个顺序，对于这类题目，往往只考虑相邻的两个进行排序即可。

优先队列

一些题目需要支持插入，删除，和求最值，所以经常使用数据结构堆。

区间覆盖

思路大概是将所有区间按照左端点，或者右端点排序，然后进行进一步贪心。

按左端点排序：
每遇到一个新区间：
如果可以做这个任务，那么就做这个任务；
如果做不了，看看能不能换之前的任务。

#include <bits/stdc++.h>
using namespace std;
int n, e, z;
pair<int, int> a[1000020];
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++) {
		if (e <= a[i].first) {
			e = a[i].second;
			z++;
		} else {
			e = min(e, a[i].second);
		}
	}
	printf("%d\n", z);
	return 0;
}

按右端点排序：
每遇到一个新区间：
如果可以做这个任务，那么就做这个任务；

#include <bits/stdc++.h>
using namespace std;
int n, e, z;
pair<int, int> a[1000020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].second, &a[i].first);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (e <= a[i].second) {
			e = a[i].first;
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

参考题目

Luogu P1012
拼数，只需要考虑相邻两个字符串，谁在前面字典序更大，谁就在前面。

bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}

Luogu P1223
接水问题，将所有人按接水时间排序。

Luogu P1080
国王游戏，只需要考虑相邻两个谁在前面更好，按乘积排序。

Luogu P1803
线段覆盖问题，将所有区间排序，进行贪心。

Luogu P1090
合并果子，每次合并最小的两个，用堆优化。

Luogu P3620
数据备份，贪心每次选择最小的数字a[i]。
将a[i-1], a[i], a[i+1]变为a[i-1]+a[i+1]-a[i]。

贪心

P2356 弹珠游戏

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

题目背景

元宵节不放假挺郁闷的，于是时间机智的改到了星期6一整天！

题目描述

MedalPluS 和他的小伙伴 NOIRP 发掘了一个骨灰级别的游戏——超级弹珠。

游戏的内容是：在一个 n*n 的矩阵里，有若干个敌人，你的弹珠可以摧毁敌人，但只能攻击你所在的行、列里的所有敌人，然后你就可以获得他们的分数之和，现在请你选择一个你的位置，使得能击杀的敌人最多，注意，你不能和敌人在一个地方。

输入格式

输入有两行，第一行一个正整数 n，接下来 n 行，每行 n 列，如果有敌人则为一个正整数，否则为 0

输出格式

输出共一行，最多分数，如果连你的容身之地都没有，请输出“Bad Game!”

样例 #1

样例输入 #1
4
1 1 1 0
1 1 1 1
1 1 1 1
0 1 1 1
样例输出 #1
6

提示

送分题，客官请拿好，(*__*) 嘻嘻……

【数据范围】

对于 30%的数据，1≤n≤10

对于 100%的数据，1≤n≤1000，保证容身之地的数量小于 10000

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, z = -1;
int a[1020][1020];
int r[1020];
int c[1020];
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &a[i][j]);
			r[i] += a[i][j];
			c[j] += a[i][j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!a[i][j])
			{
				z = max(z, r[i] + c[j]);
			}
		}
	}
	if (z < 0)
	{
		puts("Bad Game!");
	}
	else
	{
		printf("%d\n", z);
	}
	return 0;
}

题解

P2813 母舰

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

题目背景

广东汕头聿怀初中 Train#3 Problem 1

（有没有红警既视感~）

题目描述

在小A的星际大战游戏中，一艘强力的母舰往往决定了一场战争的胜负。一艘母舰的攻击力是普通的MA(Mobile Armor)无法比较的。

对于一艘母舰而言，它是由若干个攻击系统和若干个防御系统组成的。两艘母舰对决时，一艘母舰会选择用不同的攻击系统去攻击对面母舰的防御系统。当这个攻击系统的攻击力大于防御系统的防御力时，那个防御系统会被破坏掉。当一艘母舰的防御系统全部被破坏掉之后，所有的攻击都会攻击到敌方母舰本身上去造成伤害。

这样说，一艘母舰对对面的伤害在一定程度上是取决于选择的攻击对象的。

在瞬息万变的战场中，选择一个最优的攻击对象是非常重要的。所以需要写出一个战斗系统出来，判断出你的母舰最多能对对手造成多少伤害并加以实现。

输入格式

输入第一行两个整数M和N，表示对方母舰的防御系统数量和你的母舰的攻击系统数量。

接着M行每行一个整数每一个表示对方防御系统的防御力是多少。

接着N行每行一个整数每一个表示己方攻击系统的攻击力是多少。

输出格式

输出仅有一行，表示可以造成的最大伤害。

样例 #1

样例输入 #1
3 5 
1000 
2000 
1200 
2100 
2000 
1200 
1000 
1000
样例输出 #1
2000

提示

对于80%的数据有 1 <= N , M <= 1000

对于100%的数据有 1 <= N , M <= 100000

对样例的解释：

对方防御系统有3个，防御值为1000(a),2000(b),1200(c)，己方攻击系统有5个，攻击值为2100(d)，2000(e),1200(f),1000(g),1000(h)。第1轮攻击的最优方案是d攻击b，e攻击c，f攻击a，g和h攻击对方母舰本身，造成2000点伤害。

本题为转载题目~

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, z;
int a[100020];
int b[100020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &b[i]);
	}
	sort(a, a + n);
	sort(b, b + m);
	int i = 0;
	for (int j = 0; j < m; j++)
	{
		if (i < n && a[i] < b[j])
		{
			i++;
		}
		else
		{
			z += b[j];
		}
	}
	if (i < n)
	{
		z = 0;
	}
	printf("%d\n", z);
	return 0;
}

题解

P1708 天然气井

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

题目描述

Mary试图控制成都的天然气市场。专家已经标示出了最好的天然气井和中转站在成都的地图。现在需要将中转站和天然气井连接起来。每个中转站必须被连接到正好一个钻油井，反之亦然。

Mary特别指名，建设的天然气管道必须从某个天然气井开始，向南或者向东建设。Mary想知道怎么连接每个天然气井和中转站，使得需要的天然气管道的总长度最小。

输入格式

输入文件的第一行为一个正整数n(2<=n<=50000)，表示天然气井的数量（中转站的数量与之相等）。

接下来n行，每行两个整数xi和yi（0<=xi,yi<=100000），表示天然气井的坐标。向东走则x坐标增加，向北走则y坐标增加。

接下来n行，每行两个数xj'和yj'（0<=xj',yj'<=100000），表示中转站的坐标。

输出格式

输入文件第一行包含一个数，表示最短的连接管道长度。

样例 #1

样例输入 #1
3
3 5
1 2
4 3
6 3
5 2
2 1
样例输出 #1
9

提示

本题题源 POI-XIV-GAZ,请采用尽可能优的算法满足时限

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, y;
long long z;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 2 * n; i++)
	{
		scanf("%d%d", &x, &y);
		z += i < n ? y - x : x - y;
	}
	printf("%lld\n", z);
	return 0;
}

题解

P2242 公路维修问题

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

题目描述

由于长期没有得到维修，A国的高速公路上出现了N个坑。为了尽快填补好这N个坑，A国决定对M处地段采取交通管制。为了求解方便，假设A国的高速公路只有一条，而且是笔直的。现在给出N个坑的位置，请你计算，最少要对多远的路段实施交通管制？

输入格式

输入数据共两行，第一行为两个正整数N、M （2<=N<=15000，M<=N）。第二行给出了N个坑的坐标（坐标值均在长整范围内，按从小到大的顺序给出，且不会有两个点坐标相同）。

输出格式

仅一行，为最小长度和。

样例 #1

样例输入 #1
18 4
3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43
样例输出 #1
25

提示

[样例说明]

交通管制的地段分别为：3-8，14-21，25-31，40-43。

参考代码

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

题解

P5602 小E与美食

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

题目背景

小E是一个热爱美食的高中生，但吃的太多会导致他身体不舒服，他想找到一个能让他最舒服的方案，快来帮帮他！

题目描述

小E有 nn 种美食可供选择，每种美食只能吃一次，第 ii 种美食有一个美味值 aia_i，吃下一个美味值为 aia_i 的美食可以让小E的满足感提升 aia_i。

但是小E的胃是有极限的，每吃下一个美食，他的饱腹感就会提升 11。

小E最后的舒适度是他的满足感的平方除以他的饱腹感，你的目标是求出他舒适度能达到的最大值。

输入格式

第一行一个正整数 nn。

第二行 nn 个正整数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n。

输出格式

输出一行一个实数，表示小E舒适度的最大值，你的输出与标准答案的相对误差或绝对误差在 10−610^{-6} 以内即视为正确。

样例 #1

样例输入 #1
2
2 1
样例输出 #1
4.50

提示

提示

建议输出至少 88 位有效数字。

样例解释

容易发现两种美食都吃是最优的，舒适度为 (2+1)22=4.5\frac{(2+1)^2}{2} = 4.5。

数据范围

对于 30%30 \% 的数据，n,ai≤20n, a_i \le 20。

对于 50%50 \% 的数据，n,ai≤2000n, a_i \le 2000。

对于另 15%15 \% 的数据，所有 aia_i 都相等。

对于 100%100 \% 的数据，1≤n≤3×1051 \le n \le 3 \times 10^{5}，1≤ai≤1061 \le a_i \le 10^6。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[300020];
double z, s;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = n; i--;)
	{
		s += a[i];
		z = max(z, s * s / (n - i));
	}
	printf("%.8f\n", z);
	return 0;
}

题解

P1413 坚果保龄球

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

题目描述

PVZ这款游戏中，有一种坚果保龄球。zombie从地图右侧不断出现，向左走，玩家需要从左侧滚动坚果来碾死他们。

我们可以认为地图是一个行数为6，列数为60的棋盘。zombie出现的那一秒站在这一行的第60列，之后每秒向左移动一步。玩家可以随时在屏幕最某一行第一列摆放坚果，这一行的zombie瞬间全被滚过去的坚果碾死。如果zombie走到第1列没有被消灭，如果再向左走，则你的大脑就会被zombie吃掉。

现在有n只zombie！告诉你每只zombie出现的时间以及在出现的行数（可能会同时出现同一位置的僵尸），请问至少需要多少坚果才能消灭所有的zombie。

输入格式

第一行一个正整数n，表示zombie数量。

之后n行中，每行两个正整数P和t，分别表示zombie所在行和zombie出现的时间。

输出格式

一个正整数，最少需要的坚果数。

样例 #1

样例输入 #1
10
1 1
1 61
2 1
2 60
3 1
3 2
3 3
3 4
4 1
4 99999
样例输出 #1
6

提示

【数据规模】

n<=2000，t<=100000，1<=P<=6

【题目来源】

kkksc03改编

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, y, l, z;
int a[1020];
int main()
{
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		a[i] = 200000 * x + y;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		if (l + 60 <= a[i])
		{
			l = a[i];
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P5541 [USACO19FEB]Sleepy Cow Herding S

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

题目描述

Farmer John的N头奶牛，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这N头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据N个相邻的位置（例如，位置6、7、8）。

不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

输入格式

先输入一个整数N(N<=100000)，接下来输入N个数，表示N头奶牛的位置。

输出格式

输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

样例 #1

样例输入 #1
3 
4 
7 
9
样例输出 #1
1
2

提示

2019 USACO二月月赛银牌组第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[100020];
int work() {
	if (a[n - 1] == a[0] + n - 1) {
		return 0;
	}
	if (a[n - 2] == a[0] + n - 2 || a[n - 1] == a[1] + n - 2) {
		if (a[n - 1] == a[0] + n) {
			return 1;
		} else {
			return 2;
		}
	}
	int z1 = n;
	for (int i = 0; i < n; i++) {
		int p = a[i] + n - 1;
		int t = upper_bound(a, a + n, p) - a;
		z1 = min(z1, n - (t - i));
	}
	for (int i = 0; i < n; i++) {
		int p = a[i] - n + 1;
		int t = lower_bound(a, a + n, p) - a - 1;
		z1 = min(z1, n - (i - t));
	}
	return z1;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int z2 = max(a[n - 1] - a[1], a[n - 2] - a[0]) - n + 2;
	cout << work() << endl;
	cout << z2 << endl;
	return 0;
}

题解

P3650 [USACO1.3]滑雪课程设计Ski Course Design

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

题目描述

农民约翰的农场里有 nn 座山峰，每座山都有一个在 00 到 100100 之间的整数的海拔高度。在冬天,因为山上有丰富的积雪，约翰经常开办滑雪训练营。

不幸的是，约翰刚刚得知税法在滑雪训练营方面有新变化，明年开始实施。在仔细阅读法律后，他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于 1717 就要收税。因此，如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过 1717 ），约翰可以避免支付税收。

如果改变一座山 xx 单位的高度成本是 x2x^2 单位，约翰最少需要付多少钱才能使海拔最高的山峰与海拔最低的山峰的高度只差不超过 1717 约翰只愿意改变整数单位的高度。

输入格式

输入的第一行是一个整数，代表山峰的数量 nn。

第 22 行到(n+1)(n + 1) 行，每行一个整数。第 ii 行的整数 aia_i 代表第 ii 座山的海拔高度。

输出格式

输出一行一个整数，代表约翰需要支付修改山海拔高度的总金额。

样例 #1

样例输入 #1
5
20
4
1
24
21
样例输出 #1
18

提示

样例输入输出 1 解释

约翰保持高度为 44、2020 和 2121 的山的高度。他增高高度为 11 的山，变成高度 44 ，花费 32=93^2 = 9。他降低了高度为 2424 的山变成高度 2121，也花费 32=93 ^ 2 = 9。因此总共花费 9+9=189 + 9 = 18。

数据规模与约定

对于 100%100\% 的数据，1≤n≤10001 \le n \le 1000，0≤ai≤1000 \leq a_i \leq 100。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, s, z = 1e9;
int a[1020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int j = 1; j < 84; j++)
	{
		s = 0;
		for (int i = 0; i < n; i++)
		{
			int d = max(max(a[i] - j, j - 17 - a[i]), 0);
			s += d * d;
		}
		z = min(z, s);
	}
	cout << z << endl;
	return 0;
}

题解

P5650 基础字符串练习题

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

题目背景

YSGH 牛逼

题目描述

给定长度非零的非空 01 串 SS。

找出 SS 的非空连续子串 TT 满足串中 0 的个数减去 1 的个数最大。

你只需要输出最大值即可。

输入格式

一行一个 01 串表示 SS。

输出格式

一行一个数表示答案。

样例 #1

样例输入 #1
0111100101
样例输出 #1
2

提示

设 ∣S∣=n|S| = n。

数据点编号 n≤n \le
1∼21 \sim 2 1010
3∼63 \sim 6 103{10}^3
7∼107 \sim 10 105{10}^5

对于 100%100\% 的数据，1≤n≤1051 \le n \le {10}^5。

参考代码

#include <bits/stdc++.h>
using namespace std;
int x, s, z;
int main()
{
	z = -1;
	while (scanf("%1d", &x) != EOF)
	{
		s = max(s, 0) + 1 - 2 * x;
		z = max(z, s);
	}
	printf("%d\n", z);
	return 0;
}

题解

P2695 骑士的工作

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

题目背景

你作为一个村的村长，保卫村庄是理所当然的了.今天，村庄里来了一只恶龙，他有n个头，恶龙到处杀人放火。你着急了。不过天无绝人之路，现在来了一个骑士团。里面有m位成员（往下看）

题目描述

每个人都可以砍掉一个大小不超过（<=）z的头，要money个金币，求最小花费。

输入格式

第一行两个整数 n m

下接n行，一个整数 表示n个头的大小。

下接m行，每个人可以砍的头大小或金币(金币==头的大小）。

输出格式

一个整数，最小花费。如果无解，输出“you died!”

样例 #1

样例输入 #1
2 3
5 
4
7 
8
4
样例输出 #1
11

提示

1<=n,m<=20000

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, z;
int a[20020];
int b[20020];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &b[i]);
	}
	sort(a, a + n);
	sort(b, b + m);
	for (int i = 0, j = 0; j < m; j++)
	{
		if (i < n && a[i] <= b[j])
		{
			z += b[j];
			i++;
		}
		if (i == n)
		{
			printf("%d\n", z);
			return 0;
		}
	}
	printf("you died!\n");
	return 0;
}

题解

P6568 [NOI Online #3 提高组] 水壶

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

题目描述

有 nn 个容量无穷大的水壶，它们从 1∼n1\sim n 编号，初始时 ii 号水壶中装有 AiA_i 单位的水。

你可以进行不超过 kk 次操作，每次操作需要选择一个满足 1≤x≤n−11\le x\le n-1 的编号 xx，然后把 xx 号水壶中的水全部倒入 x+1x+1 号水壶中。

最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

输入格式

第一行一个正整数 nn，表示水壶的个数。

第二行一个非负整数 kk，表示操作次数上限。

第三行 nn 个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量 A1A_1, A2A_2, ⋯\cdots, AnA_n。

输出格式

一行，仅一个非负整数，表示答案。

样例 #1

样例输入 #1
10
5
890 965 256 419 296 987 45 676 976 742
样例输出 #1
3813

提示

数据规模与约定

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k, x;
int a[1000020];
int s, z;
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x);
		s += x;
		z = max(z, s);
		s -= a[i % k];
		a[i % k] = x;
	}
	printf("%d\n", z);
	return 0;
}

题解

P2095 营养膳食

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

题目描述

Mr.L 正在完成自己的增肥计划。

为了增肥，Mr.L 希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。

Mr.L 通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过 11 份，鱼类不宜吃超过 11 份，蛋类不宜吃超过 11 份，蔬菜类不宜吃超过 22 份。

Mr.L 想要在营养膳食的情况下吃到更多的脂肪，当然 Mr.L 的食量也是有限的。

输入格式

第一行包含三个正整数 n,mn,m 和 kk。表示 Mr.L 每顿饭最多可以吃 mm 份食品，同时有 nn 种食品供 Mr.L 选择，而这 nn 种食品分为 kk 类。

第二行包含 kk 个不超过 1010 的正整数，表示可以吃 11 到 kk 类食品的最大份数。

接下来 nn 行每行包括 22 个正整数，分别表示该食品的脂肪指数 aia_i 和所属的类别 bib_i。

输出格式

包括一个数字即 Mr.L 可以吃到的最大脂肪指数和。

样例 #1

样例输入 #1
6 6 3
3 3 2
15 1
15 2
10 2
15 2
10 2
5 3
样例输出 #1
60

提示

对于 100%100\% 的数据，1≤n≤2001\leq n\leq 200，1≤m≤1001\leq m\leq 100，1≤k≤1001\leq k\leq 100，1≤ai≤1001\leq a_i\leq 100，1≤bi≤k1\leq b_i\leq k。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, z;
int b[220];
pair<int, int> a[220];
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= k; i++)
	{
		scanf("%d", &b[i]);
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = n - 1; i >= 0; i--)
	{
		if (b[a[i].second] > 0 && m > 0)
		{
			b[a[i].second]--;
			m--;
			z += a[i].first;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P1484 种树

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

题目描述

cyrcyr 今天在种树，他在一条直线上挖了 nn 个坑。这 nn 个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr 不会在相邻的两个坑中种树。而且由于 cyrcyr 的树种不够，他至多会种 kk 棵树。假设 cyrcyr 有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

输入格式

第一行，两个正整数 n,kn,k。

第二行，nn 个整数，第 ii 个数表示在直线上从左往右数第 ii 个坑种树的获利。

输出格式

输出 11 个数，表示 cyrcyr 种树的最大获利。

样例 #1

样例输入 #1
6 3 
100 1 -1 100 1 -1
样例输出 #1
200

提示

对于 20%20\% 的数据，n≤20n\leq 20。

对于 50%50\% 的数据，n≤6000n\leq 6000。

对于 100%100\% 的数据，n≤500000n\leq 500000，k≤n2k\leq \dfrac{n}{2}，在一个地方种树获利的绝对值在 10610^6 以内。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[500020];
int nxt[500020];
int pre[500020];
set<pair<long long, int> > s;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		s.insert(make_pair(a[i], i));
		pre[i] = i - 1;
		nxt[i] = i + 1;
	}
	nxt[0] = 1;
	pre[n + 1] = n;
	a[0] = -1e18;
	a[n + 1] = -1e18;
	long long z = 0;
	for (int i = 0; i < k; i++) {
		int x = s.rbegin()->second;
		s.erase(--s.end());
		if (a[x] < 0) {
			break;
		}
		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;
}

题解

P1012 拼数

考虑相邻2个

21
2

2
23

21 2
2 21

#include <bits/stdc++.h>
using namespace std;
int n;
string s[30];
bool cmp(const string &a, const string &b) {
	// a 是否应该在 b 前面
	return a + b > b + a;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (s[j - 1] + s[j] < s[j] + s[j - 1])
			{
				swap(s[j - 1], s[j]);
			}
		}
	}
//	sort(s, s + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << s[i];
	}
	cout << endl;
	return 0;
}

13 312 343
343 312 13

P1223 排队接水

如果一个人，倒数第i个接水
那么有i个人等他接水，消耗的时间t * i
所以接得快的，先接
接得慢的，后接

考虑相邻2个

加强版，每个人不仅有时间，还有重要性
求一个接水顺序，使得所有人 等待时间t*重要性p 之和最小
有 0/0 的排序

bool cmp(pair<int, int> a, pair<int, int> b)
{
//	return a.first / a.second < b.first / b.second;
	return a.first * b.second < b.first * a.second;
}

可以处理0/x和x/0，但是不能处理0/0的情况

0/0 == 1/2
0/0 == 2/1

P1970 花匠

折线，不需要随机

只关注相邻2个数字的大小关系
l = a[i-1]
x = a[i]

f表示最后一步是上升的 最大长度
g表示最后一步是下升的 最大长度

#include <bits/stdc++.h>
using namespace std;
int n, l, x, f = 1, g = 1;
int main() {
	scanf("%d%d", &n, &l);
	for (int i = 1; i < n; i++) {
		scanf("%d", &x);
		if (x > l) {
			f = g + 1;
		} else if (x < l) {
			g = f + 1;
		}
		l = x;
	}
	printf("%d\n", max(f, g));
	return 0;
}

P1190 接水问题

每次处理一个，可以用堆优化

P2127 序列排序

轮换，有2种方法，选较小的
(8, 1) (4, 2) (5, 3) (3, 4) (2, 5) (7, 6)
(2, 5) (3, 4) (4, 2) (5, 3) (7, 6) (8, 1)

1 <- 5 <- 6 <- 1
2 <- 4 <- 3 <- 2

P1208 [USACO1.3]混合牛奶 Mixing Milk

排序贪心
注意到价格范围比较小，可以用计数排序

CF3B Lorry

排序枚举多少个1，多少个2
x 个 2
n-2x 个 1

或者是按平均价值贪心，最后剩下体积2 暴力
3 2
1 2
1 4
2 7
直接按平均价值贪心并不对
最后所有重量的LCM大小的背包需要暴力

P1803 凌乱的yyy / 线段覆盖

区间排序，贪心

按区间左端点排序

#include <bits/stdc++.h>
using namespace std;
int n, e, z;
pair<int, int> a[1000020];
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++) {
		if (e <= a[i].first) {
			e = a[i].second;
			z++;
		} else {
			e = min(e, e[i].second);
		}
	}
	printf("%d\n", z);
	return 0;
}

按区间右端点排序

#include <bits/stdc++.h>
using namespace std;
int n, e, z;
pair<int, int> a[1000020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].second, &a[i].first);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (e <= a[i].second) {
			e = a[i].first;
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

bzoj 1909
按终点排序怎么做？

for(i=0;i<a[m].size();i++)
{
	if(a[m][i].x>=*s.begin()) // 如果能接待这艘船一定接待。
	{
		s.erase(--s.upper_bound(a[m][i].x)); // 谁来接待？需要找s中<=a[m][i].x最大的数字。
		s.insert(a[m][i].y);
		z++;
	}
}

给定 接待容量，问最多可以接待多少船
问至少 多少接待容量，可以接待所有船

s.clear();
for(i=0;i<a[m].size();i++)
{
	if(s.size() > 0 && a[m][i].x>=*s.begin())
	{
		s.erase(s.begin());
		s.insert(a[m][i].y);
	}	
	else if(a[m][i].y<*(--s.end()))
	{
		s.insert(a[m][i].y);
	}
}

s.size()是答案

P1031 均分纸牌

最小次数 问有多少个前缀和不为0

最小张数 所有前缀和的绝对值之和

环形均分纸牌
求前缀和

最终移动的过程中，一定是从一个位置断开
可以枚举断开的位置

s[1] s[2] ... s[n-1]

s[0] = 0
s[n] = 0

从i和i+1的位置断开

abs(0-s[i])
abs(s[1]-s[i])
...
abs(s[i-1]-s[i])
abs(s[i]-s[i])
abs(s[i+1]-s[i])
abs(s[i+2]-s[i])
...
abs(s[n-1]-s[i])

一共n项
相当于找一个数字到所有数字距离之和最小
中位数
abs(x - y) x到y的距离

前缀和中位数

P1209 [USACO1.3]修理牛棚 Barn Repair

排序，选最大的间隔

CF1157C1 Increasing Subsequence (easy version)

取两边较小的，如果两边相等，那么比较一下哪边更多

CF839B Game of the Rows

优先分配4，
如果4不够，2个2可以当一个4用
如果2不够，1个4可以当一个2用

CF835B The number on the board

优先把较小的数字改成9

int i;
for(i=0;i<len && he < k;i++)
{
he+=9-a[i];
}
printf("%d\n", i);

CF1214C Bad Sequence

直接暴力
剩下为空串，或剩下)(
才有解
直接判断(S)是不是有解的
只有一种括号的括号序列判定，不需要栈，只需要计数

CF1175D Array Splitting

最大的k个后缀和

include<bits/stdc++.h>

using namespace std;
const int N=1e6+5;
long long n,k,ans,a[N];
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for (int i = n; i >= 1; i--)
{
a[i] += a[i + 1];
}
sort(b+2,b+n+1,greater());
for(int i=1;i<=k;i++)
ans+=b[i];
printf("%lld",ans);
return 0;
}

CF1213F Unstable String Sort

排序，拓扑排序

CF985C Liebig's Barrels

排序

CF808C Tea Party

直接计算，从大到小依次填满

P2698 [USACO12MAR]Flowerpot S

双指针法 相当于

2 4
4 10
6 3
12 15
[2, 4]
[4, 6]
[6, 12]
双指针法

P4085 [USACO17DEC]Haybale Feast G

P4552 [Poetize6] IncDec Sequence

双指针法
输入一个长度为n的数组，和s
找出最短的一段，和>=s

abc245_e Wrapping Chocolate

https://atcoder.jp/contests/abc245/tasks/abc245_e
n个巧克力，第i个巧克力宽A[i]长B[i]
m个盒子，第i个盒子宽C[i]长D[i]
每个盒子至多装1个巧克力
如果A[i]<=C[j]&&B[i]<=D[j]那么第i个巧克力可以被装进第j个盒子中
问能不能把所有巧克力都装进盒子

spoj ADACUT

https://www.spoj.com/problems/ADACUT/
排序贪心

spoj SVAREA11

  1. 贪心
    1. 简单介绍
    2. 排序
    3. 优先队列
    4. 区间覆盖
    5. 参考题目
  2. 贪心
    1. P2356 弹珠游戏
    1. P2813 母舰
    2. P1708 天然气井
    3. P2242 公路维修问题
    4. P5602 小E与美食
    5. P1413 坚果保龄球
    6. P5541 [USACO19FEB]Sleepy Cow Herding S
    7. P3650 [USACO1.3]滑雪课程设计Ski Course Design
    8. P5650 基础字符串练习题
    9. P2695 骑士的工作
    10. P6568 [NOI Online #3 提高组] 水壶
    11. P2095 营养膳食
    12. P1484 种树
    13. P1012 拼数
    14. P1223 排队接水
    15. P1970 花匠
    16. P1190 接水问题
    17. P2127 序列排序
    18. P1208 [USACO1.3]混合牛奶 Mixing Milk
    19. CF3B Lorry
    20. P1803 凌乱的yyy / 线段覆盖
    21. P1031 均分纸牌
    22. P1209 [USACO1.3]修理牛棚 Barn Repair
    23. CF1157C1 Increasing Subsequence (easy version)
    24. CF839B Game of the Rows
    25. CF835B The number on the board
    26. CF1214C Bad Sequence
    27. CF1175D Array Splitting
  3. include<bits/stdc++.h>
    1. CF1213F Unstable String Sort
    1. CF985C Liebig's Barrels
    2. CF808C Tea Party
    3. P2698 [USACO12MAR]Flowerpot S
    4. P4085 [USACO17DEC]Haybale Feast G
    5. P4552 [Poetize6] IncDec Sequence
    6. abc245_e Wrapping Chocolate
    7. spoj ADACUT
    8. spoj SVAREA11
≡