AcWing《算法基础课》第6章 贪心
区间
区间选点
给定N个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点,输出选择的点的最小数量。
思路
- 将每个区间按照右端点从小到大进行排序
ed
值初始化为无穷小,从前往后枚举区间- 如果遍历到的区间的左端点大于记忆区间的右端点(放有点),则把记忆区间更新成当前遍历的区间(只更新右端点,因为只在右端点放点)
证明
- 假设ans是最优解,cnt是可行解,显然有ans≤cnt
- 由于算法最后得出cnt个两两不相交的区间,覆盖每个区间至少需要cnt个点,因此ans≥cnt
- 综上所述ans=cnt
核心代码
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r;
}
}range[N];
sort(range, range + n);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (range[i].l > ed)
{
ed = range[i].r; // 在当前区间的右端点放一个点
res ++ ;
}
printf("%d\n", res);
最大不相交区间数量
可以参考区间选点那题,二者在算法思路上是一致的
- 将每个区间按照右端点从小到大进行排序
ed
表示当前放置在数轴上的点的位置,开始初始化为无穷小,表示没有放置,此时数轴上没有点- 依次遍历排序好的区间。如果区间的左端点大于当前放置点的位置,说明当前点无法覆盖区间,则把点的位置更新成该区间的右端点,表示在该区间的右端点放置一个新的点,同时更新点的个数
证明
- 假设ans是最优解,表示最多有ans个不相交的区间;cnt是可行解,表示算法求出个不相cnt交的区间,显然有ans≥cnt
- 反证法证明ans≤cnt。假设ans>cnt,由最优解的含义知,最多有ans个不相交的区间,因此至少需要ans个点才能覆盖所有区间,而根据算法知,只需cnt个点就能覆盖全部区间,且cnt<ans,这与前边分析至少需要ans个点才能覆盖所有区间相矛盾,故ans≤cnt
- 综上所述ans=cnt
核心代码
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return r < W.r; // 使sort()按右端点升序排序
}
}range[N];
// main
sort(range, range + n); // 按右端点升序排序
int res = 0, ed = -2e9; // ed为无穷小
for (int i = 0; i < n; i ++ )
if (ed < range[i].l)
{
// 找到一个无法由当前点覆盖的区间
ed = range[i].r; // 在数轴上放入新的点
res ++ ; // 更新数轴上点的个数
}
区间分组
给定N个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
思路
- 左端点排序,从前往后处理每个区间
- 判断能否将其放到某个现有的组中
- 如果不存在,则开新组放入
- 如果存在,则放进该组并更新该组的最大右端点
证明
- 假设ans是最优解,表示最少需要ans个组;cnt是可行解,表示算法找到cnt个组,显然有ans≤cnt
- 考虑在开辟第cnt个组的过程:算法此时已经开辟了cnt−1个组,组内区间两两不相交,组间区间有交集,且当前遍历区间的左端点均小于各组所有区间中最大的右端点,即当前遍历的区间一定与各组区间相交,此时必须要开辟新的组放入新的区间,因此至少需要cnt个组,即ans≥cnt
- 综上所述ans=cnt
核心代码
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];
// main
sort(range, range + n); // 按左端点升序排序
priority_queue<int, vector<int>, greater<int>> heap; // 小根堆,保存每组的最大右端点
for (int i = 0; i < n; i ++ )
{
if (heap.empty() || range[i].l <= heap.top()) heap.push(range[i].r); // 比所有组最大右端点都小
else {
heap.pop(); // 合并到右端点最小的组,并更新该组的最大右端点
heap.push(range[i].r);
}
}
printf("%d\n", heap.size()); // 小根堆元素个数为组数
说明
range[i].l <= heap.top()
等价于range[i].l <= min(heap)
,表示比各组最大的右端点还要小,使得min
的代价变为O(1)- 小根堆内并没有真的存储各组区间,而只是存储各组的最大右端点,当区间的左端点比各组右端点都小时,说明都冲突,需要开辟新组;否则只需把右端点最小的组的右端点更新成当前区间的右端点
区间覆盖
给定N个闭区间[ai,bi]以及一个线段区间[s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
思路
- 将所有区间按左端点从小到大排序
- 从前往后依次枚举每个区间,在所有能覆盖
start
的区间中选择右端点最大的区间,并将start更新成右端点的最大值
证明
- 假设ans是最优解,表示最少需要ans个区间;cnt是可行解,表示算法找到cnt个区间满足覆盖,显然有ans≤cnt
- 采用反证法证明ans≥cnt
- 假设最优解由k个区间组成,各区间按右端点从小到大排序,右端点依次记为a1,a2,⋯,ak,显然一定有t≤ak,否则最优解没有覆盖到线段区间[s,t]的右端点t,不满足覆盖条件
- 同理,假设算法求得m(m>k)个区间,各区间按右端点从小到大排序,右端点依次记为b1,b2,⋯,bk,⋯,bm,显然一定有bk<t≤bm
- t≤bm是为了满足覆盖条件
- bk<t是因为bk不是最后一个区间的端点,如果bk≤t,则
- 考虑最优解和贪心算法各自获得的第1个区间的右端点a1和b1,由于贪心算法选取右端点距离起点s最大的区间,故一定有a1≤b1
- 贪心算法又以b1为起点,找一个右端点距离b1最大的区间,最优解选取的第2个区间的右端点a2不可能超过b2,否则存在一个区间的长度a2−a1大于b2−b1,这与贪心算法矛盾,故一定有a2≤b2
- 同理一定有ak≤bk,由于bk<t,故ak<t,这说明最优解没有覆盖线段区间[s,t],矛盾
- 故ans≥cnt
- 综上所述ans=cnt
核心代码
struct Range
{
int l, r;
bool operator< (const Range &W)const
{
return l < W.l;
}
}range[N];
// main
sort(range, range + n); // 按左端点升序排序
int res = 0;
bool success = false;
for (int i = 0; i < n; i ++ )
{
// 贪心算法核心部分
int j = i, r = -2e9;
while (j < n && range[j].l <= st) // 保证覆盖起点(起点是会变化的)
{
r = max(r, range[j].r); // 选取距离起点最大的点(实际上只需看右端点的大小,因为起点是固定的,不影响max的选取)
j ++ ;
}
// 如果所有区间的右端点都比起点小,则无解
if (r < st)
{
res = -1;
break;
}
res ++ ;
// 满足条件,结束
if (r >= ed)
{
success = true;
break;
}
st = r; // 更新起点
i = j - 1; // 指针直接跳转到合适的地方迭代(双指针法)
}
if (!success) res = -1;
printf("%d\n", res);
Hoffman树
有n个结点,每次合并两个结点需要消耗两个结点值之和的能量,求一种能量消耗最少的方案,使得所有结点合并成一个。
这里与合并石子的区别在于,合并石子只能合并相邻的两堆,而这里允许任意两个合并,并不一定是相邻的。
思路
每次选取最小的两个结点合并,直至全部合并成一个结点
证明
命题1:最小的两个点深度一定最深,且可以互为兄弟
命题2:最优树用一个非叶结点代替这两个结点后,依旧是最优树
命题1一定成立,否则交换两个点,一定会使总和减少,与最优树定义矛盾。
证明命题2等价于证明这是最优子结构。考虑等式f(k+1)=f(k)+a+b,其中a和b是k+1个结点构成的树中,值最小的两个。在k个结点构成的树中,用一个新的叶节点代替了这两个结点。假设选取的不是a和b,显然新选结点的和会大于之前选的结点的和,故得到的不是最优树,因此这样构造的树一定是最优树,故满足最优子结构
核心代码
priority_queue<int, vector<int>, greater<int>> heap; // 用小根堆存储元素,加快最小值的查找
int res = 0;
while (heap.size() > 1) // 合并成1个
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();
res += a + b;
heap.push(a + b);
}
排队打水
有 n 个人排队到 1 个水龙头处打水,第 i个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?
第1个人等待的时间是0,第2个人等待的时间是t1,第3个人等待的时间是t1+t2,…,第n−1个人等待的时间是t1+t1+⋯+tn−2,第n个人等待的时间是t1+t1+⋯+tn−1
因此所有人的等待时间之和:
0+(t1)+(t1+t2)+(t1+t2+t3)+⋯+(t1+t2+⋯+tn−1)=t1(n−1)+t2(n−2)+⋯+tn−1
思路
当t1,t2,⋯,tn按升序排列时,所有人的等待时间最少。
证明
反证法:假设i<j且ti>tj,则可以交换二者,总时间会减少,说明原来不是最少的时间,矛盾。
核心代码
sort(t, t + n); // 默认升序排序
reverse(t, t + n); // 改成降序
long long res = 0;
for (int i = 0; i < n; i ++ ) res += t[i] * i;
货仓选址
数轴上有n个点,在数轴上找一个点,使得那n个点到这个点的距离之和最小
假设升序排序后的n个数为x1,x2,⋯,xn
总距离可表示为
f(x)=|x1−x|+|x2−x|+⋯+|xn−x| =(|x1−x|+|xn−x|)+(|x2−x|+|xn−1−x|)+⋯ ⩾
由排序不等式知,当n是奇数时,当且仅当在中位数取到等号;当n是偶数,则当且仅当在两个中位数之间都能取到等号
核心代码
sort(a, a + n);
int res = 0;
for (int i = 0; i < n; i ++ ) res += abs(a[i] - a[n / 2]); // q[n / 2]为中位数
说明
- 如果n是奇数,则
n / 2
是中位数下标 - 如果n是偶数,则
n / 2
是靠左的中位数下标,由于在a_{n/2}~a_{n/2 + 1}之间(包括端点)都能取到等号,故可以和奇数一致选取下标为n/2
的数
耍杂技的牛
有n头牛,第i头牛的重量为w_i,强壮值为s_i,一头牛的危险系数定义为这头牛上边的重量之和减去这头牛的强壮值,求一种顺序,使得n头牛最大的危险系数最小
思路
按w_i+s_i升序排序
证明
假设best是最优解,表示最小的危险系数;ans是可行解,表示算法找到危险系数,显然有best \le ans
反证法证明best \ge ans。假设w_i+s_i>w_{i+1} + s_{i+1},可得下表
各项同时去掉w_1+w_2+\cdots +w_{i-1},得
各项同时加上s_i + s_{i+1},得
由于w_i+s_i \ge s_i且w_i+s_i \ge w_{i+1}+s_{i+1},故w_i+s_i \ge \max\{s_i, w_{i+1}+s_{i+1} \},进而\max \{ s_{i+1}, w_i + s_i \} \ge \max\{s_i, w_{i+1}+s_{i+1} \}
故交换后n头牛的最大危险系数要么减少,要么不变,总之不会增加
假设最优解有满足这样条件的两头牛,则把它们交换后,最大危险系数会下降,与最优解的定义矛盾,故最优解一定满足这样按w_i+s_i升序排序的条件,即best \ge ans
综上所述best=ans
核心代码
typedef pair<int, int> PII;
PII cow[N];
// 读入
scanf("%d%d", &w, &s);
cow[i] = {w + s, w}; // first为二者和,second为重量
// main
sort(cow, cow + n); // 按w+s升序排序
int res = -2e9, sum = 0; // 初始化为无穷小
for (int i = 0; i < n; i ++ )
{
int s = cow[i].first - cow[i].second, w = cow[i].second; // 读取s和w
res = max(res, sum - s); // 更新最大危险系数
sum += w; // 第0~i头牛的重量之和(由上到下)
}
说明
- 最上边的牛的危险系数不是0,而是-s