贪心算法(c++)

一、贪心算法介绍

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

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

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

贪心类型多且杂，需要积累联系。

二、贪心算法实现步骤

1、确定问题的最优子结构（贪心往往跟排序、优先队列等一起出现）。

2、构建贪心选择的策略，可能通过“分类讨论”、“最小代价”、“最大价值”等方式来思考贪心策略。简单验证贪心的正确性，采用句式一般是：这样做一定不会使得结果变差、不存在比当前方案更好的方案等等。

3、通过贪心选择逐步求解问题，直到得到最终解。

三、例题

1、蓝桥OJ3412 最小化战斗力差距

https://www.lanqiao.cn/problems/3412/learning/?page=1&first_category_id=1&problem_id=3412

思路：

简单排序模型。

要将战斗力分为两部分，假设有一个a数组，一个b数组。将战斗力排序后进行划分，左边的在a数组中，右边的在b数组中，a数组的最后一个和b数组第一个元素的差距即战斗力差距，其他元素都可以忽略，故枚举即可。找间隙最小。

#includeusing 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+1,a+1+n);int ans = a[2] - a[1];for (int i = 1; i  1){ll x = pq.top(); pq.pop();ll y = pq.top(); pq.pop();ans += x + y;pq.push(x+y);}cout > n;for (int i = 1; i > a[i];sort(a+1,a+1+n);int l = 1, r = n, ans = 0;while(l > s + 1;sort(s+1,s+1+n);if (s[1] == s[n])//字符串全相等{for (int i = 1; i