贪心算法练习题（最小化战斗力差距、谈判、纪念品分组、分糖果）
贪心算法练习题（最小化战斗力差距、谈判、纪念品分组、分糖果）
一、贪心算法的介绍
贪心的基本原理:每一步都选择局部最优解，而尽量不考虑对后续的影响，最终达到全局最优解。
贪心的局限性:贪心算法不能保证获得全局最优解，但在某些问题上具有高效性。
贪心的特征:贪心选择性质、最优子结构性质(根据我的观察，很多贪心的题目会出现“不同的操作产生的贡献相同”的特征，在此特征下我们每次选择代价最小的)。
贪心的类型多且杂，难以划分，需要不断练习和积累。
二、贪心算法的实现步骤
1.确定问题的最优子结构(贪心往往和排序、优先队列等一起出现) 2.构建贪心选择的策略，可能通过 “分类讨论”、“最小代价”、“最大价值” 等方式来思考贪心策略。简单验证贪心的正确性，采用句式一般是：这样做一定不会使得结果变差、不存在比当前方案更好的方案等等。 3.通过贪心选择逐步求解问题，直到得到最终解。
三、最小化战斗力差距
问题描述
小蓝是机甲战队的队长，他手下共有n名队员，每名队员都有一个战斗力值wi。现在他需要将这 n 名队友分成两组 a和b，分组必须满足以下条件:
每个队友都属于 a 组或b组。
a 组和b组都不为空。
战斗力差距最小。
战斗力差距的计算公式为|max(a)- min(b)|，其中 max(a)表示 a 组中战斗力最大的，min()表示b组中战斗力最小的。 请你计算出可以得到的最小战斗力差距。
输入格式
第一行一个整数 n，表示队员个数。 第二行 n 个整数 w1, w2, w3......wn，分别表示每名队友的战斗力值。数据范围保证:2 ≤n ≤ 1e5,1 ≤ wi≤ 1e9
输出格式
输出一个整数，表示可以得到的最小战斗力差距
简单排序模型。 要将战斗力分为两部分，为了使得差距最小，我们可以将战斗力排序后，找一个位置进行划分，使得左边的都在a，右边的都在b，从而这个差距就是这个位置两边的战斗力差距，说明差距的取值仅有n-1种，枚举即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N];
int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a, a + n);
int ans = a[2] - a[1];
for (int i = 1; i < n; i++)
ans = min(ans, (a[i + 1] - a[i]));
cout << ans;
return 0;
}四、谈判
总操作数一定情况下的最小代价模型我们知道这里一共需要进行的操作次数一定是n-1次，那么贪心地想，如果每次选择代价最小的两个部落合并，不仅可以使得当前代价最小，还可以使得后续合并的代价也尽可能小。部落大小通过优先队列来维护
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
priority_queue<ll, vector<ll>, greater<ll>> pq;
// 声明一个最小堆（优先队列），元素类型为ll（长整型）
int main() {
int n;cin >> n;
// 循环n次，每次读取一个整数并添加到优先队列中
for(int i = 1; i <= n; ++i) {
ll x; cin >> x; // 从标准输入读取一个整数x，用于存储每次输入的整数
pq.push(x); // 将x添加到优先队列pq中
}
ll ans = 0; // 定义一个长整型变量ans，用于存储最终的答案
while (pq.size() > 1) { // 当优先队列中还有多于一个元素时
ll x = pq.top(); // 获取队列顶部的元素（最小的元素）
pq.pop(); // 弹出队列顶部的元素
ll y = pq.top(); // 再次获取队列顶部的元素（当前最小的元素）
pq.pop(); // 再次弹出队列顶部的元素
ans += x + y; // 将x和y相加，并将结果累加到ans上
pq.push(x + y); // 将x和y的和添加到队列中
}
cout << ans << "\n";
return 0;
}五、纪念品分组
题目描述
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为了使参加晚会的同学所获得的纪念品价值相对均衡，乐乐需要将购来的纪念品根据价格进行分组。但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数 w。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是编写一个程序，找出所有分组方案中分组数最少的一种，并输出最少的分组数目。
输入描述
- 第1行包括一个整数 w（80 ≤ w ≤ 200），表示每组纪念品价格之和的上限。
- 第2行为一个整数 n（1 ≤ n ≤ 30000），表示购来的纪念品的总件数。
- 第3 ~ n+2行，每行包含一个正整数pi（5 ≤ pi ≤ w），表示所对应纪念品的价格。
输出描述
输出一个整数，表示最少的分组数目。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N];
int main() {
int w, n;
cin >> w >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int l = 1, r = n, ans = 0;
while (l <= r) {
ans++; // 每进入一次循环，就增加一组
if (a[l] + a[r] <= w) {
l++; // 如果当前左右两个元素之和小于等于w，则左指针向右移动
}
r--; // 无论是否满足条件，右指针都向左移动
}
cout << ans << '\n';
return 0;
}六、分糖果
最少数目的贪心模型
为了最小化所需的组数，我们应尽可能让每组都装满两件礼物。贪心策略是：每次选取最贵的礼物，并尝试为它配对一个最便宜的礼物，以确保每组的容量得到最大化利用。这样做既高效又实用，因为最贵与最便宜的礼物组合往往能最有效地占满一组的容量。通过这种策略，我们可以实现组数的最小化。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int main() {
int n, x;
cin >> n >> x;
cin >> s + 1; // 从数组s的第2个位置开始读取字符串
sort(s + 1, s + 1 + n); // 对字符串进行排序
if (s[1] == s[n]) {
// 如果第一个字符和最后一个字符相同
for (int i = 1; i <= n / x + (n % x ? 1 : 0); ++i) {
cout << s[1];
}
} else if (s[1] == s[x]) {
// 如果第一个字符和位置x上的字符相同
for (int i = x; i <= n; ++i) {
cout << s[i];
}
} else {
// 其他情况
cout << s[x];
}
return 0;
}今天就先到这了！！！
腾讯云开发者
