信息学奥赛一本通 1422：【例题1】活动安排

【题目链接】

ybt 1422：【例题1】活动安排

【题目考点】

1. 贪心

【解题思路】

该题属于区间选点问题，ybt 1324：【例6.6】整数区间 是给定一些区间，选择一些点使得每个区间范围内至少有1个点。
本题为：给定一些区间，选择一些点使得每个区间范围内至少有给定数量的点。
本题中，每个地块可以看作数轴上的一个点，“B和E之间最少种T棵树”，指的是在区间[B, E]中至少选择T个点。

贪心选择：对每个区间，如果还需要选点，则尽量从区间右侧选点。
所有区间按照右端点$E$从小到大排序，排序后第i区间范围为$[B_i,E_i]$，其中需要至少选择$T_i$个点。
贪心选择的具体解释：

• 如果该区间中已经选择点的数量大于等于$T_i$，则不需要再选点。
• 如果该区间中已经选择点的数量小于$T_i$，则从$E_i$到$B_i$从大到小遍历每个点，遇到未选择的点就选择该点，直到选够$T_i$个点。

贪心选择性质的证明：

1. 证明存在最优解包含第一次的贪心选择
   第一次的贪心选择为：在$[B_1,E_1]$中选择区间$[E_1-T_1+1,E_1]$中的整数点，共$T_1$个点。
   反证法：假设所有最优解都不包含第一次的贪心选择
   也就是说在$[B_1,E_1-T_1]$选择了一些点，而$[E_1-T_1+1,E_1]$中存在未被选择的点。设在$[B_1,E_1-T_1]$中选择了点$G$，而$[E_1-T_1+1,E_1]$中点$F$未被选择。
   现在不选择点$G$转而选择点$F$，第2、第3等后面的区间中已选择的点可能会增加，也可能不变。每个区间的选点数量都满足要求，总选点数量不变。因此这样变换选择点后，此时的选点方案仍然是最优解。
   将在$[B_1,E_1-T_1]$中选择的所有点都去掉，转而在$[E_1-T_1+1,E_1]$中选择相同数量的点，最后选择的点就是$[E_1-T_1+1,E_1]$中的每个点，这也就是进行了贪心选择，这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖，原命题得证。
2. 假设最优解包含前k次的贪心选择，证明存在最优解包含第k+1次的贪心选择：
   证明过程与第1点的证明过程相似，不再赘述。

具体实现：
设vis数组，vis[i]表示第i点是否已被选择。
对于每个区间，先遍历整个区间，统计出已选点数量，也就是求出待选择点的数量。

• 如果待选择点的数量为0，就看下一个区间。
• 否则，从区间右端点开始，向前遍历，遇到未选择的点，就选择一个点，直到待选择点的数量为0。统计选点总数量，就是问题结果。

【题解代码】

解法1：贪心

#include<bits/stdc++.h>//贪心选择性质：按区间右端点升序排序，每个区间尽量选后面的数字 
using namespace std;
struct Node
{
	int b, e, t;//[b, e]中选t个数 
};
bool cmp(Node a, Node b)
{
	return a.e < b.e;
}
bool vis[30005];//vis[i]:点i是否已被选择 
int main()
{
	Node a[5005];
	int n, m, ans = 0;//ans：总选点数量 
	cin >> n >> m;
	for(int i = 1; i <= m; ++i)
		cin >> a[i].b >> a[i].e >> a[i].t; 
	sort(a+1, a+1+m, cmp);
	for(int i = 1; i <= m; ++i)
	{
		for(int j = a[i].b; j <= a[i].e; ++j) 
			if(vis[j] && --a[i].t <= 0)//a[i].t这里表示区间中还需要选择几个点
				break;
		if(a[i].t <= 0) 
			continue;
		for(int j = a[i].e; j >= a[i].b; --j) if(!vis[j])
		{
			vis[j] = true;
			ans++;
			if(--a[i].t <= 0)
				break;
		}
	}
	cout << ans;
	return 0;
}