贪婪和果实(Huffman树)排队去打水(顺序不等式；货舱选址；绝对值不等式；杂技牛(推公式) ) ) ) ) ) ) ) ) ) ) ) ) )。
上篇博客小编主要介绍“贪婪问题(一)区间问题”，博客链接
本文主要通过四个例题介绍与“Huffman树、顺序不等式、绝对值不等式、估计式”相关的贪婪问题。
水果(Huffman树)主题说明：
主题链接
想法：
两个点合并为一个点，最终合并为一个点，图像点成为树的前端，可以视为一棵树。 样品如下所示。
我们描绘一般情况(完全二叉树)，所有叶子的节点)是我们合并的点。
如图所示，我们消费的总额如下。
从3a 3b 3c 3d 2e 2f叶节点到顶点通过几个父节点计算多少次？ 拿出贪婪的战略：
一次选择最小的两个合并。
证明
(1)权重最小的两点可以是一定深度最深且互为兄弟节点。 如果权重最小的点不在最深的位置，换到最深的位置一定比不更换好。 因为从叶的节点到顶点通过几个父节点会计算几次。 列出这两种情况的合计值的减法与0比较就能得到。 第一步可以合并最小的两座山
)2) n-1的最优解是n的最优解吗？ 这里毫无疑问这是最佳解，但具体证明后，我跳过了。 请注意，在某些问题中，n-1的最优解不一定是n的最优解
我们在小根山上一次取出最小的两点。 关于山，请参考这个博客的链接
# include iostream # include algorithm # includequeueusingnamespacestd； intmain(void ) { int n； scanf('%d '，n )； priority_queueint、vectorint、greaterint heap； wile(n---- ) { int x； 扫描(' % d '，x )； HEAP.push(x； (} int res=0； wile(heap.size ) )1) { int a=heap.top )； heap.pop (； int b=heap.top (； heap.pop (； res =a b； HEAP.push(ab； }printf('%d '，res )； 返回0； )排队打水(顺序不等式)主题说明：
主题链接
想法：
第n个同学的等待时间是第一个n-1人的打水时间的总和。 可以求出n个同学等待时间之和的最低值。
设n个同学的打水时间为t1、t2、t3…tn
于是，sum_t=t1*(n-1 ) t2* ) n-2 ) T3 * (n-3 ) ) tn * 0最佳解：按从小到大的顺序排序，总时间最小。 证明：
假设存在两个相邻元素tit(I1 )，交换位置不影响其他同学的等待时间。 前ti*(n-I ) t ) I1 ) ) n-I-1 )更换后t ) I1 ) ) n-I ) ti* ) n-I-1 ) )
由于两者减去了ti-t(I1 ) 0，因此更换前的等待时间大于更换后的等待时间。
# include iostream # includealgorithmusingnamespacestd； const int N=1e5 10； int arr[N]； intmain(void ) { int n； cin n； for(intI=0； i n； I({CINarr[I]； }sort(arr，arr n )； 龙龙RES=0； for(intI=0； i n； I ) RES=arr[I]*(n-I-1 )； } cout res endl； 返回0； )货舱布局(绝对值不等式)问题说明：
主题链接
想法：
可以写公式，从公式的角度得出最小值。 把x作为仓库的位置。 对于每个组，可以将其视为|a - x| |b - x|的模型。 x取a-b之间时，获取最小值。
f(x ) min=xn-x1x ) n-1 )- x2 .
即需要看等号是否成立。 通过将x放在中间的两个数之间，各组可以取最小值，f(x )可以取最小值。 中央值(n为奇数)或中央值(x之间) n为偶数)
# include iostream # includealgorithmusingnamespacestd； const int N=1e5 10； int arr[N]； intmain(void ) { int n； cin n； for(intI=0； i n； I({CINarr[I]； }sort(arr，arr n )； 龙龙RES=0； for(intI=0； i n/2； I ) { res =arr[n-i-1] - arr[i]； } cout res endl； 返回0； )表演杂技的牛(推式)主题说明：
主题链接
想法：
写出公式，根据不等式得出最优解。 假设w[n]，s[n]已经排序，考虑用i 1头牛交换I，即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 limits.h # include iostream # includealgorithmusingnamespacestd； typedef pairint，int PII； const int N=5e4 10； int n； PII cows[N]； intmain(void ) { cin n； for(intI=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(intI=0； i n； I ) { int w=cows[i].second，s=cows[i].first - w； RES=max(RES，sum - s )； sum =w； } cout res endl； 返回0； }