贪心讲解

博主： RearWaves
发布时间：2023 年 04 月 14 日
389 次浏览
6 条评论
9124字数
分类：算法设计

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

# 贪心1

# 1 区间问题

### [905. 区间选点](https://www.acwing.com/problem/content/907/)

给定 N 个闭区间 [ai,bi], 请你在数轴上选择尽量少的点, 使得每个区间内至少包含一个选出的点. 输出选择的点的最小数量.

位于区间端点上的点也算作区间内.

**解题思路:**

1. 将每个区间按照右端点从小到大进行排序;
2. 从前往后枚举区间, end值初始化为无穷小;

- 如果本次区间不能覆盖掉上次区间的右端点,  ed < range[i].l, 说明需要选择一个新的点,  res ++ ; ed = range[i].r;
  
  ![区间选点.png](https://www.rearwaves.com/usr/assets/algorithm/greedy/652_e1356000cd-%E5%8C%BA%E9%97%B4%E9%80%89%E7%82%B9.png)
- 如果本次区间可以覆盖掉上次区间的右端点, 则进行下一轮循环.

时间复杂度 O(nlogn).

**证明:**

设 ans 为最优解,  cnt为某一个答案. 欲证: ans = cnt.

1. ans <= cnt,  显然;
2. ans >= cnt,  这里应该是容易产生困惑的地方.

首先要清楚一点, ans是一个定值、常数, 表示最优解的值;  而cnt它是一个变量, 代表某一种方案的值. 要证: ans >= cnt,  只需要证: ans >= max(cnt)即可, 因为如果连最大的cnt都不超过ans, 那么所有的cnt都小于等于ans.

何时取到max？当全部区间两两不相交时, cnt必然取到最大值. (但是, 有部分区间相交时, 也可以取到最大值, 设想一下只有2个区间, 中间相交了一小部分, 我们可以分别取第一个区间的最左, 和第二个区间的最右. 但这并不重要, 只要我们能证明, 在其中一种取到最大值的方案中, ans >= cnt, 那么剩下的全部方案的cnt必然小于等于ans. )

显然, 当全部区间两两不相交时, ans = cnt. 因此由ans >= max(cnt) >= cnt,  可证(2)也是成立的. 综上所述, 由(1)(2)可知, ans = cnt.

```c++
const int N = 1e5 + 10;
int n;
struct Range {
	int l, r;
	bool operator< (const Range& W) const {
		return r < W.r;
	}
}range[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = { l, r };
	}
	sort(range, range + n);
	int res = 0, ed = -2e9;
	for (int i = 0; i < n; i++) {
		if (range[i].l > ed) {
			res++;
			ed = range[i].r;
		}
	}
	printf("%d\n", res);
	return 0;
}
```

### [908. 最大不相交区间数量](https://www.acwing.com/problem/content/910/)

给定 N 个闭区间 [ai,bi], 请你在数轴上选择若干区间, 使得选中的区间之间互不相交(包括端点).

输出可选取区间的最大数量.

**解题思路:**

和上一个题目完全相同, 因为最大不相交区间数=最少覆盖区间点数.

因为如果几个区间能被同一个点覆盖, 说明他们相交了, 所以有几个点就是有几个不相交区间.

### [906. 区间分组](https://www.acwing.com/problem/content/908/)

给定 N 个闭区间 [ai,bi], 请你将这些区间分成若干组, 使得每组内部的区间两两之间(包括端点)没有交集, 并使得组数尽可能小.

输出最小组数.

**解题思路:**

![image_5.png](https://www.rearwaves.com/usr/assets/algorithm/greedy/652_1073c53ccd-image_5.png)

1. 将所有区间按照==左端点==进行排序;
2. 利用小根堆来维护所有组的右端点.

- 因为判断一个区间`q[i]`能否放进某个组, 条件是 $l_i>max_r$, $mar_r$指的是组内所有区间中最靠右的右端点, 如果这个区间的左端点大于组的右端点, 说明没有交集, 可以放进这个组里.
- 所以判断一个区间能否放进之前的组中, 条件是 $l_i>(max_r)_{min}$, 只要最小的比它小就一定存在, 如果最小的都比它大就一定有交集了. 所以根本不需要记录组内有哪些区间, 只需要把组的最大右端点放进小根堆里, 每次用区间的左端点和堆顶元素比较即可.

3. 从前往后遍历每一个区间

- 首先把第一个区间放进堆里`if(heap.empty())`
- 判断当前区间能否放进现有的某个组中:

如果不存在这样的组(有交集)`p[i].first<=heap.top()`, 需要新建一个组, 直接把区间的右端点放进堆里`heap.push(p[i].second)`;

如果存在这样的组(无交集)`p[i].first>heap.top()`, 可以任意找一个组放进去,  我们每次都找堆顶所在的组, **放进去=更新这个组在队中的右端点=heap.top**.

`heap.pop(); heap.push(p[i].second)`;

(先丢掉原来的右端点, 把新的右端点放进去)

**证明:**

ans:最终答案; cnt:按照给定的贪心算法得到的答案.

1. `ans>=cnt,` 首先cnt一定是合法方案(不一定是最小的), 每个组内的区间没有任何交集, ans是所有方案中的最小值, 所以`ans>=cnt`;
2. `ans<=cnt`, 假设枚举到第i个区间时, 打算把这个区间放到某个组内, 但前cnt-1个组中都有区间与当前区间有交集, 说明至少有cnt个区间有公共点l~i~, 所以这cnt个区间一定不会放到同一组中, 所以`ans>=cnt`.

```c++
const int N = 1e5 + 10;
int n;
struct Range {
	int l, r;
	bool operator< (const Range& W) const {
		return l < W.l;
	}
}range[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = { l, r };
	}
	sort(range, range + n); 
	//用小根堆维护所有组的右端点的最大值
	//堆中的每一个值存的是每个组的右端点的最大值
	priority_queue<int, vector<int>, greater<int>> heap;
	for (int i = 0; i < n; i++) {
		auto r = range[i];	//当前区间
		//堆是空的或者堆中的最小值小于当前区间的左端点,需要开一个新的组
		if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
		else {	//放在最小值的组里
			int t = heap.top();
			heap.pop();
			heap.push(r.r);
		}
	}
	printf("%d\n", heap.size());
	return 0;
}
```

**[其他解法:](https://www.acwing.com/solution/content/8902/)**

看了一下, 貌似是求最大区间厚度的问题. 大家可以把这个问题想象成活动安排问题:

**有若干个活动, 第i个活动开始时间和结束时间是[S~i~,f~i~], 同一个教室安排的活动之间不能交叠, 求要安排所有活动, 少需要几个教室？**

有时间冲突的活动不能安排在同一间教室, 与该问题的限制条件相同, 即最小需要的教室个数即为该题答案.

我们可以把所有开始时间和结束时间排序, 遇到开始时间就把需要的教室加1, 遇到结束时间就把需要的教室减1,在一系列需要的教室个数变化的过程中, 峰值就是多同时进行的活动数, 也是我们至少需要的教室数.

```c++
const int N = 100100;
int n;
int b[2 * N], idx;
int main()
{
    scanf ("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数. 
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数. 
    }
    sort(b, b + idx);
    int res = 1, t = 0;
    for(int i = 0; i < idx; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}
```

### [907. 区间覆盖](https://www.acwing.com/problem/content/909/)

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t], 请你选择尽量少的区间, 将指定线段区间完全覆盖.

输出最少区间数, 如果无法完全覆盖则输出 −1.

**解题思路:**

1. 按左端点排序;
2. 从前往后一次枚举每个区间: 判断左端点在st之前的区间, 循环找到最右端点, 如果右端点也在st之前, 说明无法覆盖. 下一次枚举的时候依旧用这个区间(i不变);
3. 如果找到左端点在st之前, 右端点在st之后的区间, (i++);
4. 每循环一次, 没有在前面跳出的话, 说明找到了一个区间, res++;
5. 如果这个区间右端点能覆盖end, 说明能覆;
6. 把start更新成right, 保证后面的区间适合之前的区间有交集, 从而形成对整个序列的覆盖;
7. 如果遍历了所有的数组, 还是没有覆盖最后的end, 说明不能成功.

```c++
const int N = 100010;
int n;
struct Range {
	int l, r;
	bool operator< (const Range& W)const
	{
		return l < W.l;
	}
}range[N];
int main() {
	int st, ed;
	scanf("%d%d", &st, &ed);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		range[i] = { l, r };
	}
	sort(range, range + n);		//按左端点排序
	int res = 0;
	bool success = false;
	for (int i = 0; i < n; i++) {
		int j = i, r = -2e9;	//维护右端点的最大值
		//在左端点<=st的区间中, 选择右端点最大的一个
		while (j < n && range[j].l <= st) {
			r = max(r, range[j].r);
			j++;
		}
		//如果最大右端点rmax小于st, 则没有能覆盖st这个点的区间了
		if (r < st) {
			res = -1;
			break;
		}
		res++;
		if (r >= ed) {	//[st,rmax]这里面的点被覆盖住了
			success = true;
			break;
		}
		st = r;	//选择右端点最大的那个区间用来覆盖[st,rmax]上的点
		i = j - 1;
	}
	if (!success) res = -1;
	printf("%d\n", res);
	return 0;
}
```

# 2 Huffman树

### [148. 合并果子](https://www.acwing.com/problem/content/150/)

在一个果园里, 达达已经将所有的果子打了下来, 而且按果子的不同种类分成了不同的堆. 达达决定把所有的果子合成一堆. 每一次合并, 达达可以把两堆果子合并到一起, 消耗的体力等于两堆果子的重量之和. 可以看出, 所有的果子经过 n−1 次合并之后, 就只剩下一堆了.

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和. 因为还要花大力气把这些果子搬回家, 所以达达在合并果子时要尽可能地节省体力. 假定每个果子重量都为 1, 并且已知果子的种类数和每种果子的数目, 你的任务是设计出合并的次序方案, 使达达耗费的体力最少, 并输出这个最小的体力耗费值.

例如有 3 种果子, 数目依次为 1, 2, 9. 可以先将 1、2 堆合并, 新堆数目为 3, 耗费体力为 3. 接着, 将新堆与原先的第三堆合并, 又得到新的堆, 数目为 12, 耗费体力为 12. 所以达达总共耗费体力=3+12=15.

可以证明 15 为最小的体力耗费值.

**解题思路:**

经典哈夫曼树的模型, 每次合并重量最小的两堆果子即可. 使用小根堆维护所有果子, 每次弹出堆顶的两堆果子, 并将其合并, 合并之后将两堆重量之和再次插入小根堆中.

每次操作会将果子的堆数减 1 , 一共操作 n−1 次即可将所有果子合并成1堆. 每次操作涉及到2次堆的删除操作和1次堆的插入操作, 计算量是 O(logn). 因此总时间复杂度是 O(nlogn).

**算法证明: **(反证法)最先合并的必定是合并次数最多的, 合并次数越多意味着这两个数加的次数越多, 加的数越大那么自然答案也会变大, 这样就不是最优解了, 所以每次必须合并两堆最小的. 剩下每次合并同理.

```c++
int main() {
	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\n", res);
	return 0;
}
```

# 3 排序不等式

### [913. 排队打水](https://www.acwing.com/problem/content/description/915/)

有 n 个人排队到 11 个水龙头处打水, 第 i 个人装满水桶所需的时间是 t~i~, 请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

**解题思路:**

首先, 我们先想一种直觉上的做法. 每次选一个当前序列中最小的一个数, 然后让`res`加上本次的在总序列中耗费的时间, 也就是 $t_i × (n−i−1)$, 其中, $t_i$ 是排好序中当前最小的, n 是数的个数, i  是第 i 个元素. 然后我们再来证明它的正确性. 假设有这样一个最优解序列$cnt$ , 排好序的序列中有一个数 $cnt_x$ , 它的下一个数比它小, 如果两数交换, $(n−i−1) × cnt_i - (n−i) × cnt_x$ 的下一个数, 差一定是严格>0的, 这就和它是最优解矛盾了, 所以最优解序列一定是单调上升的.

```c++
const int N = 1e5 + 10;
int n;
int t[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &t[i]);
	sort(t, t + n);
	LL res = 0;
	for (int i = 0; i < n; i++) res += t[i] * (n - i - 1);
	printf("%lld\n", res);
	return 0; 
}
```

# 4 绝对值不等式

### [104. 货仓选址](https://www.acwing.com/problem/content/106/)

在一条数轴上有 N 家商店, 它们的坐标分别为 A1∼AN. 现在需要在数轴上建立一家货仓, 每天清晨, 从货仓到每家商店都要运送一车商品.

为了提高效率, 求把货仓建在何处, 可以使得货仓到每家商店的距离之和最小.

**解题思路:**

1. 把`A[0]~A[N-1]`排序, 设货仓在`X`坐标处, `X`左侧的商店有`P`家, 右侧的商店有`Q`家. 若`P < Q`, 则每把仓库的选址向右移动1单位距离, 距离之和就会变少`Q - P`.同理, 若`P > Q`, 则仓库的选址向左移动会使距离之和变小. 当`P==Q`时为最优解.
2. 因此仓库应该建在中位数处, 把A进行排序,

- 当N为奇数时, 货仓建在`A[(N - 1)/2]`处,
- 当N为偶数时, 仓库建在`A[(N - 1)/2 + 1]`处.

```c++
const int N = 1e5 + 10;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	sort(a, a + n);
	int res = 0;
	for (int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]);
	printf("%d\n", res);
	return 0; 
}
```

# 5 推公式

### [125. 耍杂技的牛](https://www.acwing.com/problem/content/127/)

农民约翰的 N 头奶牛(编号为 1..N)计划逃跑并加入马戏团, 为此它们决定练习表演杂技. 奶牛们不是非常有创意, 只提出了一个杂技表演: 叠罗汉, 表演时, 奶牛们站在彼此的身上, 形成一个高高的垂直堆叠. 奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序.

这 N 头奶牛中的每一头都有着自己的重量 W[i] 以及自己的强壮程度 S[i]. 一头牛支撑不住的可能性取决于它头上所有牛的总重量(不包括它自己)减去它的身体强壮程度的值, 现在称该数值为风险值, 风险值越大, 这只牛撑不住的可能性越高.

您的任务是确定奶牛的排序, 使得所有奶牛的风险值中的最大值尽可能的小.

**解题思路:**

危险值 = 它前面奶牛的重量(w)之和 - 自身强壮值(s). 因为危险值和 w、s 都有关, 所以可以将每头牛的 w+s 排序.

**证明:**

假设 $w_{i}+s_{i}>w_{i+1}+s_{i+1}$ :

|        |           第 i 个位置的牛            |             第 i+1 个位置的牛              |
| :----: | :----------------------------------: | :----------------------------------------: |
| 交换前 |  $w_{1}+w_{2}+\ldots+w_{i-1}-s_{i}$  | $\quad w_{1}+w_{2}+\ldots+w_{i}-s_{i+1} $  |
| 交换后 | $w_{1}+w_{2}+\ldots+w_{i-1}-s_{i+1}$ | $w_{1}+w_{2}+\ldots+w_{i-1}+w_{i+1}-s_{i}$ |

在两边同时加上 $-\left(w_{1}+w_{2}+\ldots+w_{i-1}\right)+s_{i}+s_{i+1}$ , 则:

|        | 第 i 个位置的牛 | 第 i+1 个位置的牛 |
| :----: | :-------------: | :---------------: |
| 交换前 |    $s_{i+1}$    |   $w_{i}+s_{i}$   |
| 交换后 |     $s_{i}$     | $w_{i+1}+s_{i+1}$ |

易得 $w_{i}+s_{i}=\max \left\{s_{i+1}, w_{i}+s_{i}, s_{i}, w_{i+1}+s_{i+1}\right\}$. 因此, 对于位置越小的 i, $w_{i}+s_{i}$ 越小越好.

```c++
const int N = 5e4 + 10;
int n;
PII cow[N];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int w, s;
		scanf("%d%d", &w, &s);
		cow[i] = { w + s, w };
	}
	sort(cow, cow + n);
	int res = -2e9, sum = 0;
	for (int i = 0; i < n; i++) {
		int w = cow[i].second, s = cow[i].first - w;
		res = max(res, sum - s);
		sum += w;
	}
	printf("%d\n", res);
	return 0;
}
```

最后修改：2023 年 04 月 14 日

如果觉得我的文章对你有用，请随意赞赏

6 条评论

dvlafvodtu
October 5th, 2024 at 07:57 pm

看的我热血沸腾啊www.jiwenlaw.com

回复
jbbnknwfgc
October 4th, 2024 at 09:08 pm

想想你的文章写的特别好https://www.ea55.com/

回复
lwdgpbdtsp
October 1st, 2024 at 08:42 pm

看的我热血沸腾啊https://www.237fa.com/

回复
rczlizwaqs
September 23rd, 2024 at 08:59 am

想想你的文章写的特别好

回复
jeijjxxddd
September 22nd, 2024 at 10:44 pm

叼茂SEO.bfbikes.com

回复
nhtidgibqj
September 22nd, 2024 at 06:10 pm

博主真是太厉害了！！！

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

贪心讲解
评论数： 6
搜索初步
评论数： 5
图论初步
评论数： 4
欢迎使用 Typecho
评论数： 2
比赛常用技巧及库函数
评论数： 2

dvlafvodtu
看的我热血沸腾啊www.jiwenlaw.com
usukxmmttv
不错不错，我喜欢看 www.jiwenlaw.com
dcyfmsthoa
想想你的文章写的特别好www.jiwenlaw.com
jbbnknwfgc
想想你的文章写的特别好https://www.ea55.com/
igbbiexfym
想想你的文章写的特别好https://www.ea55.com/

基础算法初步
评论数： 0
欢迎使用 Typecho
评论数： 2
图论初步
评论数： 4
搜索初步
评论数： 5
竞赛常识
评论数： 2

贪心讲解

RearWaves • 2023 年 04 月 14 日

# 贪心1

# 1 区间问题

### [905. 区间选点](https://www.acwing.com/problem/content/907/)

给定 N 个闭区间 [ai,bi], 请你在数轴上选择尽量少的点, 使得每个区间内至少包含一个选出的点. 输出选择的点的最小数量.

位于区间端点上的点也算作区间内.

**解题思路:**

1. 将每个区间按照右端点从小到大进行排序;
2. 从前往后枚举区间, end值初始化为无穷小;

时间复杂度 O(nlogn).

**证明:**

设 ans 为最优解,  cnt为某一个答案. 欲证: ans = cnt.

1. ans <= cnt,  显然;
2. ans >= cnt,  这里应该是容易产生困惑的地方.

显然, 当全部区间两两不相交时, ans = cnt. 因此由ans >= max(cnt) >= cnt,  可证(2)也是成立的. 综上所述, 由(1)(2)可知, ans = cnt.

### [908. 最大不相交区间数量](https://www.acwing.com/problem/content/910/)

给定 N 个闭区间 [ai,bi], 请你在数轴上选择若干区间, 使得选中的区间之间互不相交(包括端点).

输出可选取区间的最大数量.

**解题思路:**

和上一个题目完全相同, 因为最大不相交区间数=最少覆盖区间点数.

因为如果几个区间能被同一个点覆盖, 说明他们相交了, 所以有几个点就是有几个不相交区间.

### [906. 区间分组](https://www.acwing.com/problem/content/908/)

给定 N 个闭区间 [ai,bi], 请你将这些区间分成若干组, 使得每组内部的区间两两之间(包括端点)没有交集, 并使得组数尽可能小.

输出最小组数.

**解题思路:**

![image_5.png](https://www.rearwaves.com/usr/assets/algorithm/greedy/652_1073c53ccd-image_5.png)

1. 将所有区间按照==左端点==进行排序;
2. 利用小根堆来维护所有组的右端点.

3. 从前往后遍历每一个区间

- 首先把第一个区间放进堆里`if(heap.empty())`
- 判断当前区间能否放进现有的某个组中:

如果不存在这样的组(有交集)`p[i].first<=heap.top()`, 需要新建一个组, 直接把区间的右端点放进堆里`heap.push(p[i].second)`;

如果存在这样的组(无交集)`p[i].first>heap.top()`, 可以任意找一个组放进去,  我们每次都找堆顶所在的组, **放进去=更新这个组在队中的右端点=heap.top**.

`heap.pop(); heap.push(p[i].second)`;

(先丢掉原来的右端点, 把新的右端点放进去)

**证明:**

ans:最终答案; cnt:按照给定的贪心算法得到的答案.

**[其他解法:](https://www.acwing.com/solution/content/8902/)**

看了一下, 貌似是求最大区间厚度的问题. 大家可以把这个问题想象成活动安排问题:

**有若干个活动, 第i个活动开始时间和结束时间是[S~i~,f~i~], 同一个教室安排的活动之间不能交叠, 求要安排所有活动, 少需要几个教室？**

有时间冲突的活动不能安排在同一间教室, 与该问题的限制条件相同, 即最小需要的教室个数即为该题答案.

### [907. 区间覆盖](https://www.acwing.com/problem/content/909/)

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t], 请你选择尽量少的区间, 将指定线段区间完全覆盖.

输出最少区间数, 如果无法完全覆盖则输出 −1.

**解题思路:**

# 2 Huffman树

### [148. 合并果子](https://www.acwing.com/problem/content/150/)

可以证明 15 为最小的体力耗费值.

**解题思路:**

# 3 排序不等式

### [913. 排队打水](https://www.acwing.com/problem/content/description/915/)

有 n 个人排队到 11 个水龙头处打水, 第 i 个人装满水桶所需的时间是 t~i~, 请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

**解题思路:**

# 4 绝对值不等式

### [104. 货仓选址](https://www.acwing.com/problem/content/106/)

在一条数轴上有 N 家商店, 它们的坐标分别为 A1∼AN. 现在需要在数轴上建立一家货仓, 每天清晨, 从货仓到每家商店都要运送一车商品.

为了提高效率, 求把货仓建在何处, 可以使得货仓到每家商店的距离之和最小.

**解题思路:**

- 当N为奇数时, 货仓建在`A[(N - 1)/2]`处,
- 当N为偶数时, 仓库建在`A[(N - 1)/2 + 1]`处.

# 5 推公式

### [125. 耍杂技的牛](https://www.acwing.com/problem/content/127/)

您的任务是确定奶牛的排序, 使得所有奶牛的风险值中的最大值尽可能的小.

**解题思路:**

危险值 = 它前面奶牛的重量(w)之和 - 自身强壮值(s). 因为危险值和 w、s 都有关, 所以可以将每头牛的 w+s 排序.

**证明:**

假设 $w_{i}+s_{i}>w_{i+1}+s_{i+1}$ :

在两边同时加上 $-\left(w_{1}+w_{2}+\ldots+w_{i-1}\right)+s_{i}+s_{i+1}$ , 则:

易得 $w_{i}+s_{i}=\max \left\{s_{i+1}, w_{i}+s_{i}, s_{i}, w_{i+1}+s_{i+1}\right\}$. 因此, 对于位置越小的 i, $w_{i}+s_{i}$ 越小越好.

6 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

贪心讲解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款