贪心问题（二）-huffman树、排序不等式、绝对值不等式、推公式

贪心问题

• 合并果子（Huffman树）
• 排队打水（排序不等式）
• 货仓选址（绝对值不等式）
• 耍杂技的牛（推公式）

上篇博客小编主要介绍了“贪心问题（一）–区间问题”， 博客链接
这篇主要以四道例题来介绍“Huffman树、排序不等式、绝对值不等式、推公式”有关的贪心问题。

合并果子（Huffman树）

题目描述：

题目链接

思路：

1. 两点可以合并成1点，最终汇聚成一点（形象点就是树尖），可以看成一棵树。样例如图所示：
   

2. 我们画出一般情况（完全二叉树），所有叶子节点（红色表示）是我们要合并的点。
   
   如图所示，我们消耗的总值为：
   3a + 3b + 3c + 3d + 2e + 2f叶子节点到顶点经过几个父节点就会算多少次。得出贪心策略：
   每一次挑出最小的两堆合并。

证明

（1）权值最小的两个点，一定深度最深且可以互为兄弟节点。如果权值最小的点不在深度最深的位置，那么交换到最深的位置，一定会比不交换更优。因为叶子节点到顶点经过几个父节点就会算多少次。 列出这两种情况的总值相减跟0比较即可得出。 可以得出----第一步可以合并最小两堆
（2） n-1的最优解是n的最优解吗？小编在这肯定这个是最优解，但具体证明，我就略过去了。切记，有的问题中，n-1的最优解不一定是n的最优解

我们用小根堆来每次取出最小的两点， 关于堆，大家可以参考这篇博客博客链接

#include 
#include 
#include 
using namespace std;
int main(void){int n;scanf("%d", &n);priority_queue<int, vector<int>, greater<int>> heap;while(n --){int x;scanf("%d", &x);heap.push(x);}int res = 0;while(heap.size() > 1){int a = heap.top();heap.pop();int b = heap.top();heap.pop();res += a + b;heap.push(a + b);}printf("%d", res);return 0;
}

排队打水（排序不等式）

题目描述：

题目链接

思路：

1. 第n个同学的等待时间是前n-1个的打水时间合。n个同学的等待时间之和最下值即为所求。
   设n个同学的打水时间为t1, t2, t3…tn
   则，sum_t = t1 * (n-1) + t2 * (n-2) + t3 * (n-3) ....+ tn * 0
2. 最优解：从小到大排序，总时间最小。

证明：

假设存在两相邻元素ti > t(i+1), 交换一下位置，不会影响其他同学等待时间。交换前ti * (n - i) + t(i+1) * (n-i-1) 交换后t(i+1) * (n - i) + ti *( n - i - 1)
两者相减得ti - t(i+1) > 0 所以交换前的等待时间大于交换后的等待时间。

#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main(void){int n;cin >> n;for(int i = 0; i < n; i ++){cin >> arr[i];}sort(arr, arr + n);long long res = 0;for(int i = 0; i < n; i ++){res += arr[i] * (n - i - 1);}cout << res <<endl;return 0;
}

货仓选址（绝对值不等式）

问题描述：

题目链接

思路：

1. 我们可以写出公式，从公式角度推出最小值。设x为仓库位置。
   

对于每一组可以看成|a - x| + |b - x| 的模型。当x取到a-b之间时，取得最小值。
f(x)min >= xn - x1 + x(n-1) - x2 + ...
即需要看等号是否成立。让x在中间两数之间即可使得每组都能取得最小值， 即可使得f(x)取得最小值。x取得中位数(n为奇数)，或中间俩x之间（n为偶数）

#include 
#include 
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main(void){int n;cin >> n;for(int i = 0; i < n; i ++){cin >> arr[i];}sort(arr, arr+n);long long res = 0;for(int i = 0; i < n/2; i ++){res += arr[n-i-1] - arr[i];}cout << res << endl;return 0;
}

耍杂技的牛（推公式）

题目描述：

题目链接

思路：

1. 写出公式，根据不等式推出最优解。
2. 假设w[n]、 s[n]已经排好序, 我们考虑将i与i+1头牛交换，即w[i]、s[i]和w[i+1]、s[i + 1]交换有什么变化，考虑局部特征。下面计算的是，交换前后第i、i+1头牛的值（当然w、s数组值并未变化。）。
   

交换前：Xi前 = w[1] + …+w[i-1] - s[i];
X[i+1]前 = w[i] + …w[i-1]+w[i] - s[i+1]
交换后：Xi后=w[1] +…w[i - 1]+w[i+1] - s[i]
X[i+1]后=w[1]+…+w[i-1] - s[i+1]
当把相同项去掉后，发现交换前后最大值：

交换前最大值便是w[i] - s[i+1]
交换后最大值便是：w[i+1] - s[i]
只要满足w[i] + s[i] > w[i+1]+s[i+1] 交换这两头牛，就会使得危险系数得最大值降低。

#include 
#include 
#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10;
int n;
PII cows[N];int main(void){cin >> n;for(int i = 0; i < n; i ++){int w, s;cin >> w >> s;cows[i] = {w + s, w};}sort(cows, cows + n);int sum = 0, res = INT_MIN;for(int i = 0; i < n; i ++){int w = cows[i].second, s = cows[i].first - w;res = max(res, sum - s);sum += w;}cout << res << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！