【算法/题目训练】：贪心练习

IsLand1314

发布于 2025-02-12 09:45:58

7200

代码可运行

文章被收录于专栏：学习之路学习之路

运行总次数：0

代码可运行

一、前言

🔥 之前在这篇文章里【算法/训练】：贪心（算法理论学习及实践）讲了贪心的知识，以及对于其的练习，这里的话我们就纯练习题目了，也是对之前的文章的补充，以后有关于贪心算法的题目也基本会放到这篇博客里面的

二、练习

1. 最大整数

点击题目链接 题目描述

现在有 n 个正整数，将他们连成一排，组成一个最大的整数。
例如，现在有三个整数 13,312,343，连接成最大整数为 34331213。

输入

第一行一个整数 n。（1≤n≤100000）
第二行 n 个不超过 int 类型范围的正整数。

输出输出一个数表示组成的最大整数。

样例输入
3
121 12 96
样例输出
9612121

贪心策略

我们不考虑整体的最大，先考虑局部的最大，假如有 A B 两个整数，要使 A B 组合起来最大的话，则需要判断一下

A B > BA，则 A 在 B 的前面，对于 string 类型而言，就相当于比较 A+B 和 B+A
此时按照上面策略得到的整体就是最大整数

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(const string& a, const string& b)
{
	return a + b > b + a;
}
int main()
{
	vector<string> arr;
	string s;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		arr.push_back(s);
	}
	sort(arr.begin(), arr.end(),cmp);
	for (int i = 0; i < n; i++) {
		cout << arr[i];
	}
	return 0;
}

2. 删数

点击题目链接 题目描述

输入一个高精度的正整数 n（长度不大于 240 位），去掉其中任意 s 个数字后剩下的数字按原左右次序将组成一个新的正整数，现求一种方案，使得新的正整数数值最小。

输入

第一行一个整数 n。
第二行一个正整数 s。

输出

输出一个数表示最小值，输出时忽略数字的前导零。

样例输入
179566
4
样例输出
15

贪心策略

局部：每次删除一个离最高位最近的逆序位数字，比如 1234321，其中 43 是离最高位最近的逆序位，删除 4 即可
整体：此时按照上面策略执行 n 次得到的整体就是最小整数

#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	string n;
	int s;
	cin >> n >> s;
	for (int i = 0; i < s; i++) {
		int j = 0;
		while (n[j + 1] && n[j] <= n[j + 1]) j++;
		while (n[j]) { // 字符串前移
			n[j] = n[j + 1];
			j += 1;
		}
	}
	for (int i = 0, f = 1; n[i]; i++) {
		if (n[i] == '0' && f) continue; // 找第一个非0数
		cout << n[i];
		f = 0;
	}
	return 0;
}

3. 独木舟

点击题目链接 题目描述

一群人去旅行，要租用独木舟，每艘独木舟最多乘两人，且所有独木舟有一个统一的载重限度。给出独木舟的载重限度和每个人的体重，现求最少需要租用多少独木舟。

输入

第一行一个整数 w，表示独木舟的载重量。（80≤w≤200）
第二行一个整数 n，表示旅游人数。（1≤n≤30000）
接下来 n 行，每行一个数表示 ai，即每个人的重量（5≤ai≤w）

输出

输出一个数表示最少需要的独木舟数量。

样例输入
100
9
90 20 20 30 50 60 70 80 90
样例输出
6

贪心策略

局部：每次把最轻的和最重的放一个船上，如果放不了的话，就把最重的先放船上，而这个最轻的就和安排最重之后的剩余人中重的坐一个船
整体：此时按照上面策略得到的就是最少独木舟数量
解题步骤：先对数组进行排序，然后再比较

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int w, n;
	cin >> w >> n;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int l = 0, r = n - 1;
	int cnt = 0; // 独木舟数量
	while (l < r){
		if (a[l] + a[r] <= w) l++;
		r--;  // 先把重的安排出去
		cnt++;
	}
	if (l == r) cnt++; // 刚好有一个人单独的话
	cout << cnt << endl;
	return 0;
}

4. 最大子阵和

点击题目链接 题目描述

给定一个矩阵，在其中找一个子矩阵，使得子矩阵中所有元素的和加在一起最大

输入

第一行输入一个整数 N 表示矩阵的大小为 N∗N。
接下来 N 行，每行 N 个数，表示矩阵中的元素的值 C。（−128≤C≤127）

输出

输出一个整数，表示最大子阵和。

样例输入
4
0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2
样例输出
15

这个题目我们先分析一下，假如我们现在确定了子矩阵的起始行和终止行，那么我们要在当前子矩阵中找最大的子矩阵（行确定了，只需要确定拿几列的子矩阵最大就行），那么就需要对每一行进行相加，将这个子矩阵就变成了一维的子序列，那么现在就变成求出当前子序列的最大子序和而最大子序和问题的贪心策略如下：

局部： s 代表以前一个位置为结尾的最大子序和，当前值为 a，如果 s>= 0，则 s += a，否则 s = a
整体：按照如上策略执行，过程中 s 的最大值就变成了最大子序和

上面的起始行和终止行我们通过枚举来获取，而每一列的和值通过前缀和进行运算，这个方便获取起始行到终止行的列和值

比如我们要获取 [i,j] 行第 k 列的和值，那么就需要 a[j][k] - a[i - 1][k]（前缀和差分）

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			arr[i][j] += arr[i - 1][j]; // 前缀和
		}
	}

	int res = INT32_MIN; // 记录最大值
	for (int i = 1; i <= n; i++) {//起始行
		for (int j = i; j <= n; j++) { //终止行(注意：终止行一定要 >= 起始行)
			int s = 0;
			for (int k = 1; k <= n; k++) { // 起始行到终止行每列
				int a = arr[j][k] - arr[i - 1][k]; // 差分
				if (s >= 0) s += a;
				else s = a;
				if (s > res) res = s;
			}
		}
	}
	cout << res << endl;
	return 0;
}

上面

s_i

可以表示以 i 位置为结尾的最大子序和，i 位置的值为

a_i

，则

s_i = max(a_i , s_{i-1}+a_i)

那么为啥

s_i

表示这个最大子序和呢？证明如下：

当 i = 0，此时

s_i

肯定是以 i 位置结尾的最大值

当 i = 1 时候，此时

s_i

要么是

a_i

，要么就是

s_0

a_i

，此时获得

s_i

肯定也是最大的，同理往后推获得肯定是以 i 位置结尾的最大值

那么上面我们最开始 s = 0，

s_i

表示以 i 位置结尾的最大子序和，那么

s_{i+1}

arr_i

，或者等于

arr_i + s_i

，但是如果我们的

s_i

< 0的话，后者一定是比前者小的，毕竟 + 一个负数肯定是变小，总不可能变大吧

5. 最小操作次数

点击题目链接 题目描述

给出两个整数 a,b，每次操作可以把 a 变成 a+1 或 a∗k 。求把 a 变成 b 至少需要几步操作。

输入

第一行三个数 a,b,k。（0≤a,b,k≤

10^{18}

）

接下来 N 行，每行 N 个数，表示矩阵中的元素的值 C。（−128≤C≤127）

输出

输出最少操作次数。

样例输入
2 10 2
样例输出
3

贪心策略

局部：ans 表示最小操作次数，则 ans 更新策略如下：
- 情况一：若 a*k <= b，则 ans += 1 + b %k，b /= k
- 情况二：若 a*k > b，则 ans += b - a，终止
整体：按照如上策略执行最终得到的 ans 就是最大操作次数

#include <iostream>
using namespace std;

int main()
{
	long long a, b, k; // 注意数据范围
	cin >> a >> b >> k;
	if (k == 0) {
		if (b == 0) cout << 0 << endl;
		else cout << b - a << endl;
	}
	else if (k == 1) {
		cout << b - a << endl;
	}
	else {
		long long ans = 0;
		while (1) {
			if (a * k <= b) {
				ans += 1 + b % k;
				b /= k;
			}
			else {
				ans += b - a;
				break;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

对上面贪心策略的理解，首先我们需要知道两个结论，如下：

使用

\times k

操作肯定是优于 +1 操作，这个是肯定的吧，毕竟

\times k

达到

a \times k

只需要一步，而＋1 到达

a \times k

需要

(a - 1) \times k

步

当 a 为 b 的数字前缀时，再使用

\times k

操作

比如：a 为 12，b 为 1432，k 为 10的情况，我们应该先给 a 的后缀 +1 +1，使其变成 14 成为 b 前缀，然后

\times 10

，得到 140，同样再 +1 +1 +1 ，再

\times 10

就可以得到 b了

6. 安装雷达

点击题目链接 题目描述

地图 x 轴的上方为海，下方为陆地，海中有 n 个小岛，坐标分别为 (

X_i

Y_i

)。有一种雷达，能探测到的范围为以 d 为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都处在探测范围内。注意雷达是建在海岸线上的，也就是x轴上的。

输入

第一行输入两个数 n,d。（1≤n≤1000）
接下来 n 行，每行两个数代表小岛的坐标。（−1000≤

X_i

Y_i

≤1000）

输出

输出一个数表示答案，无解时输出 −1。

样例输入
3 2
1 2
-3 1
2 1
样例输出
2

这个题目我们先分析一下，这个题目其实并不是圆圈范围问题的，而是一个数据映射的问题，下面画个图理解一下：

那么现在雷达可以放的位置就在 [a, b] 这个区间里面
那么现在问题就变成了，有若干个区间，在每个区间里面至少放置一个雷达，求放置雷达的最少数量

贪心策略

局部：安装区间 [

l_i

r_i

] 结束位置从小到大排序，雷达放在区间末尾，pos 代表最后一个雷达的位置，若 pos <

l_i

，雷达数量 +1，此时pos =

r_i

整体：按照如上策略执行最终得到的雷达数量就是最小的

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef struct Node {
	double l, r; // 存储每个岛屿雷达区间
};

bool cmp(const Node& a, const Node& b) {
	return a.r < b.r;
}

int main()
{
	int n;
	double d;
	cin >> n >> d;
	double X, Y; 
	vector<Node> arr(n);
	for(int i = 0; i < n; i++){
		cin >> X >> Y;
		if (Y > d) {
			cout << -1 << endl;
			return 0;
		}
		// 将坐标转化为范围
		double t = sqrt(d * d - Y * Y);
		arr[i].l = X - t;
		arr[i].r = X + t;
	}
	sort(arr.begin(), arr.end(), cmp);
	int ans = 1;
	double pos = arr[0].r;// pos 记录最后一个雷达放置位置
	for (int i = 1; i < n; i++) {
		if (arr[i].l > pos) {
			ans++;
			pos = arr[i].r;
		}
	}

	cout << ans << endl;
	return 0;
}

7. 挤牛奶

点击题目链接 题目描述

有 C 头奶牛需要挤奶，每头奶牛需要在规定的时间开始挤奶，并在规定的时间结束挤奶，每头奶牛挤奶时会占据一台机器。求 C 头奶牛在规定的时间挤奶至少需要多少台挤奶机。

输入

第一行输入一个数 C。（1≤C≤50000）
接下来 C 行，每行两个数表示每头奶牛开始挤奶的时间和结束挤奶的时间。（均小于 1,000,000）

输出

第一行输出最少需要的机器数量。
接下来 C 行，每行输出一个数，表示第 i 头奶牛使用的挤奶机编号。（奶牛优先使用编号小的机器）

贪心策略

局部：按照挤奶开始时间，安排每一头奶牛，将当前奶牛安排给可以安排的编号最小的挤奶机，当无法安排时增加挤奶机数量
整体：按照如上策略执行最终得到的数量就是最小的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;

struct Node {
	int l, r;
	int id; // 奶牛原有编号，防止排序改变
}arr[N];

bool cmp(const Node& a, const Node& b) {
	if (a.l != b.l) return a.l < b.l;
	return a.id < b.id;
}

int m_time[N], ans[N];
int cnt = 0;

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		cin >> arr[i].l >> arr[i].r;
		arr[i].id = i;
	}
	sort(arr, arr + n, cmp);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int pos = -1;
		for (int j = 0; j < cnt; j++) {
			if (m_time[j] < arr[i].l) {
				pos = j; 
				break;
			}
		}
		if (pos == -1) pos = (cnt++);
		m_time[pos] = arr[i].r;
		ans[arr[i].id] = pos + 1;
	}
	printf("%d\n", cnt);
	
	for (int i = 0; i < n; i++) {
		printf("%d\n", ans[i]);
	}

	return 0;
}

8. 奶牛晒太阳

点击题目链接 题目描述

有 C 头奶牛去晒太阳，每头奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。
而刚开始的阳光的强度非常大，奶牛都承受不住，奶牛得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。
那么为了不让奶牛烫伤，又不会没有效果。给出了 L 种防晒霜固定的阳光强度和数量，每头奶牛只能抹一瓶防晒霜，求能够享受晒太阳的奶牛最多有几头。

输入

第一行输入两个数 C,L。（1≤C,L≤2500）
接下来 C 行，每行两个数表示每头奶牛能接受的阳光强度的最小值和最大值。（均小于 1000）
再接下来 L 行，每行两个数表示每种防晒霜固定的阳光强度和数量。（均小于 1000）

输出

输出能晒太阳的奶牛的最多数量

样例输入
3 2
3 10
2 5
1 5
6 2
4 1
样例输出
2

分析：

本题模型就是在数轴上给出一些线段（奶牛对应区间），然后再给出一些点，一个点能够和一条线段配对当且仅当他们有交，求最大匹配数

贪心策略

局部：将所有点从小到大排序，所有线段按右端点从小到大排序，右端点相同的话就按左端点从小到大排序，依次判断点与线段是否匹配
整体：按照如上策略执行最终得到的数量就是最大的

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Data {
	int a, b;
};

Data cow[N], item[N];

bool cmp(const Data& x, const Data& y) { 
	if (x.b != y.b) return x.b < y.b;
	return x.a < y.a;
}



int main()
{
	int C, L;
	cin >> C >> L;
	for (int i = 0; i < C; i++) cin >> cow[i].a >> cow[i].b;
	for (int i = 0; i < L; i++) cin >> item[i].b >> item[i].a; // 方便与奶牛共用一个排序函数，减少冗余代码
	sort(cow, cow + C, cmp);
	sort(item, item + L, cmp); // 防晒霜根据阳光强度排

	int ans = 0;
	for (int i = 0; i < C; i++) {
		int f = 0;
		for (int j = 0; j < L && !f; j++) {
			if (item[j].a == 0) continue; // 第 j 个防晒霜数量
			if (item[j].b <= cow[i].b && cow[i].a <= item[j].b) {
				f = 1;
				item[j].a--;
			}
		}
		ans += f;
	}
	cout << ans << endl;

	return 0;
}

9. 公司的任务

点击题目链接 题目描述

公司有 M 个任务需要完成，每个任务有一个难度系数

Y_i

并且需要一定的时间

X_i

完成。

现在有 N 台机器，每台机器有最大工作时间和最大工作难度，只有当机器的最大工作时间和最大工作难度大于等于任务的时间和任务的难度时，机器才能完成这个任务。
每天机器每天只能完成一个任务，一个任务只能被一台机器完成。当完成一个任务时，公司能获得 500∗

X_i

+2∗

Y_i

的报酬。求今天公司最多能获得的报酬。

输入

第一行输入两个整数 N,M
接下来 N 行，每行两个数，表示机器的最大工作时间和最大工作难度。
接下来 M 行，每行两个数，表示任务需要的时间和任务的难度。

输出

输出一行两个数，第一个数为能完成的最大任务数，第二个数为今天能获取的最高报酬。

样例输入
1 2
100 3
100 2
100 1
样例输出
1 50004

分析：

从上面报酬为 500∗

X_i

+2∗

Y_i

，可以知道

X_i

与

Y_i

的权重差很多，再结合数据范围 0 <

X_i

< 1400，0 <

Y_i

< 100，因此对于两个任务 (

X_i

，

Y_i

) 和 (

X_j

Y_j

)，如果存在

X_i

X_j

，那么选任务 (

X_i

，

Y_i

) 肯定报酬更大

贪心策略

局部：将所有任务以及机器按照时间从大到小排序，时间相同的按照任务难度从大到小排序，维护能够处理当前任务的所有机器，选择其中难度系数最小的
整体：按照如上策略执行最终得到的报酬就是最大的

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

struct Data {
	int x, y;
};

Data task[N], mach[N];

bool cmp(const Data& a, const Data& b) { 
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}

// 难度系数为 i 的机器数量
int cnt[105] = { 0 };

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%d%d", &mach[i].x, &mach[i].y);
	for (int i = 0; i < m; i++) scanf("%d%d", &task[i].x, &task[i].y);
	sort(mach, mach + n, cmp);
	sort(task, task + m, cmp);
	
	long long ans = 0, t_cnt = 0;

	for (int i = 0, j = 0; i < m; i++) {
		while(j < n && mach[j].x >= task[i].x) { // 机器最大工作时间 > 任务需要时间
			cnt[mach[j].y] += 1;
			j += 1;
		}
		for (int y = task[i].y; y <= 100; y++) {
			if (cnt[y] == 0) continue;
			cnt[y] -= 1;
			ans += 500 * task[i].x + 2 * task[i].y;
			t_cnt += 1;
			break;
		}
	}

	printf("%lld %lld\n", t_cnt, ans);
	return 0;
}

10. 树的颜色

点击题目链接 题目描述

有一棵树，它的所有节点都需要染色，每个节点都有一个代价基础值

C_i

。

第一个染色的是根节点，其余节点染色的时候其父节点必须已染色。
染色一个节点会用掉一个时间单位，每个节点染色的代价是染完此节点时的总时间 T 乘上这个节点的基础值

C_i

。求染完所有节点所需的最小代价。

输入

第一行包含两个整数 N,R 其中，N 是树中节点个数，R 是根节点编号。
第二行输入 N 个整数，编号为 i 的节点的代价基础值 Ci。（1≤

C_i

≤500）

接下来 N−1 行为边的信息，每行两个数分别表示父节点编号和子节点编号。

输出

输出一个整数，表示最小代价。

思路：

染色最大值节点：如果 x 是最大值节点，那么一旦 x 父节点被染色，下一个染色的一定是 x 节点
观察权值：
设置目标：先染色 y
1. T * z + (T + 1) * y + (T + 2) * x
2. T * z + (T + 1) * x + (T + 2) * z
3. 想要先染色 y，则必须满足 2 < 1，则 z < (y + x) /2，那么此时就可以把 x, y 看作一个节点
等价树形结构：T * y +(T + 1) *x = T * (y + x) + n * x (n 是 y 包含的原始节点数量)
因此原树得到最后染色代价应该是 (x + y + z) +

\Delta

即可

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e3 + 10;

int n, r;
int C[N], fa[N] = {0}; 
bool vis[N]; // 表明节点是合并过的
long long ans = 0;
int cnt[N]; // 每个节点包含原始节点数量
double w[N];// w 表示当前节点所包含节点平均值

int find_max() {
	int x = -1;
	for (int i = 1; i <= n; i++) {
		if (i == r || vis[i] == true) continue;
		if (x == -1 || w[x] < w[i]) x = i; 
	}
	return x;
}

int find_fa(int x) {
	if (vis[fa[x]]) return find_fa(fa[x]);
	return fa[x];
}

int main()
{
	cin >> n >> r;
	for (int i = 1; i <= n; i++) {
		cin >> C[i];
		ans += C[i];
		fa[i] = i; // 初始化 只有根节点父节点是自己
		w[i] = C[i];
		cnt[i] = 1;
	}

	for (int i = 1, a, b; i < n; i++){
		cin >> a >> b; // 读入每条边信息
		fa[b] = a;
	}

	// 将每个节点与其父节点合并
	for (int i = 1; i < n; i++) {
		int x = find_max(); //找权值最大的
		int fa_x = find_fa(x); // 查找 x 第一个没有被合并的节点
		ans += cnt[fa_x] * C[x];
		
		C[fa_x] += C[x];
		cnt[fa_x] += cnt[x];
		w[fa_x] = 1.0 * C[fa_x] / cnt[fa_x];
		vis[x] = true;
	}

	cout << ans << endl;
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-11，如有侵权请联系 cloudcommunity@tencent.com 删除

排序