贪心算法.

哈夫曼树

哈夫曼树（Huffman Tree），又称为霍夫曼树或最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩。
定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度（Weighted Path Length, WPL）达到最小，则称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，其中权值较大的结点离根较近。
如图：a 和 b的权值一定小于c的权值，c的权值一定小于d的权值。证明：若b > c那么交换b 和 c的位置后，该树的总权值为：3a + 3c + 2b +d，所以3a + 3c + 2b +d < 3a + 3b + 2c + d，又因为哈夫曼树的带权路径长度最小，而b > c时，使得该树的总权值增大，违反了哈夫曼树的定义，所以b < c。

题目：148. 合并果子 - AcWing题库

这道题与之前的dp石子合并，不一样。前者是严格相邻的石子堆，而后者是任意石子堆。

本道题就是典型的哈夫曼树问题，注意使用小根堆，使得最小的节点在最前面。

代码：

#include<bits/stdc++.h>using namespace std;int n;int main()
{cin >> n;priority_queue<int, vector<int>, greater<int>> q;for(int i = 0; i < n; i ++ ){int a;cin >> a;q.push(a);}int res = 0;//每次取出来前两个，并将其合并的值推回堆中while(q.size() >= 2){int x = q.top();q.pop();int y = q.top();q.pop();x += y;q.push(x);res += x;}cout << res << endl;return 0;
}

题目：913. 排队打水 - AcWing题库

思路

先对样例进行计算：第二个人所需要等待的时间为：3；第三个人用来等待的时间为：3 + 6；
第四个人所需要等待的时间为：3 + 6 + 1；第五个人用来等待的时间为：3 + 6 + 1 + 4；
第六个人：3 + 6 + 1 + 4 + 2；第六个人：3 + 6 + 1 + 4 + 2 + 5。

规律就是:所需要等待的总时间 = 第i个人打水所需要的时间 * (n - i)
公式：a[1]*(n - 1) + a[2] * (n - 2) + ... + a[n] * (n - n)。
越靠前的人，所占用的总时间的乘数更大。所以我们要尽可能的使靠前的人打水时间尽可能的小。所以对所有人打水所需要的时间大小进行排序，时间小的人先打水
证明：
假设x > y。①x * (n - i) + y * (n - i - 1) = max1; ②y * (n - i) + x * (n - i - 1) = max2
① - ② == x - y > 0，所以max1 > max2，所以应将小数放在之前总和更小。

代码：

#include<bits/stdc++.h>using namespace std;int n;
int a[100010];int main()
{cin >> n;for(int i = 1; i <= n; i ++ ) cin >> a[i];sort(a + 1, a + n + 1);long long res = 0;//下标从0开始，需多减去1for(int i = 1; i <= n; i ++) res += a[i] * (n - i);cout << res << endl;return 0;
}

题目：104. 货仓选址 - AcWing题库

若选点到a、b的总距离的最小值，如右图。那么我们扩展到多点，只要让y在所有区间内，那么选y点到所有点的总距离一定最小，而y点即是所有点的中位数

代码：

#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;int n; 
int a[100010];int main()
{cin >> n;for(int i = 0; i < n; i ++ ) cin >> a[i];sort(a, a + n);//取中点int s = a[n / 2],ans = 0;for(int i = 0; i < n; i ++ ) ans += abs(s - a[i]);cout << ans;
}

题目：125. 耍杂技的牛 - AcWing题库

思路：

这里叠罗汉是仅仅叠成一束，而非三角。

贴图来源：耍杂技的牛。
综上，我们对所有的w[ i ] + s[ i ] 求和之后进行排序，当w[ i ] + s[ i ] > w[i + 1] + s[ i + 1 ]时，交换第i与第i + 1头牛会使风险降低；否则当w[ i ] + s[ i ] <= w[i + 1] + s[ i + 1 ]时，不需要交换就能保证风险最低，所以直接对w[ i ] + s[ i ] 求和之后进行排序进行升序排序即可

代码：

#include<bits/stdc++.h>using namespace std;int n;
typedef pair<int, int> pii;pii a[50010];
int main()
{cin >> n;for(int i = 0; i < n; i ++ ){int w, s;cin >> w >> s;//对重量以及强壮程度的和进行排序a[i]={w + s, w};}sort(a, a + n);int sum = 0, res = -1e9;for(int i = 0; i < n; i ++ ){int x = a[i].first, y = a[i].second;//在所有风险值中取最大值。该危险值 = 先前总质量 - 该牛的强壮程度值res = max(res, sum - x + y);sum += y;//计算先前总质量}cout << res;return 0;
}