贪心算法练习题（最小化战斗力差距、谈判、纪念品分组、分糖果）

���录

一、贪心算法的介绍

二、贪心算法的实现步骤

三、最小化战斗力差距

四、谈判

五、纪念品分组

六、分糖果

---

一、贪心算法的介绍

贪心的基本原理:每一步都选择局部最优解，而尽量不考虑对后续的影响，最终达到全局最优解。

贪心的局限性:贪心算法不能保证获得全局最优解，但在某些问题上具有高效性。

贪心的特征:贪心选择性质、最优子结构性质(根据我的观察，很多贪心的题目会出现“不同的操作产生的贡献相同”的特征，在此特征下我们每次选择代价最小的)。

贪心的类型多且杂，难以划分，需要不断练习和积累。

二、贪心算法的实现步骤

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   using namespace std;const int N = 1e5 + 9;int a[N];int main(){int n; cin >> n;for (int i = 1; i > a[i];sort(a, a + n);int ans = a[2] - a[1];for (int i = 1; i  n;                // 循环n次，每次读取一个整数并添加到优先队列中      for(int i = 1; i > 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  w >> n;      for (int i = 1; i > a[i];      }      sort(a + 1, a + 1 + n);      int l = 1, r = n, ans = 0;      while (l  x;      cin >> s + 1; // 从数组s的第2个位置开始读取字符串        sort(s + 1, s + 1 + n); // 对字符串进行排序        if (s[1] == s[n]) {          // 如果第一个字符和最后一个字符相同          for (int i = 1; i