什么网站备案容易审核,沈阳网站建设q479185700棒,如何做婚庆公司的网站,深圳公关公司首荐乐云seo【题目链接】
ybt 1422#xff1a;【例题1】活动安排
【题目考点】
1. 贪心
【解题思路】
该题属于区间选点问题#xff0c;ybt 1324#xff1a;【例6.6】整数区间 是给定一些区间#xff0c;选择一些点使得每个区间范围内至少有1个点。 本题为#xff1a;给定一些区…【题目链接】
ybt 1422【例题1】活动安排
【题目考点】
1. 贪心
【解题思路】
该题属于区间选点问题ybt 1324【例6.6】整数区间 是给定一些区间选择一些点使得每个区间范围内至少有1个点。 本题为给定一些区间选择一些点使得每个区间范围内至少有给定数量的点。 本题中每个地块可以看作数轴上的一个点“B和E之间最少种T棵树”指的是在区间[B, E]中至少选择T个点。
贪心选择对每个区间如果还需要选点则尽量从区间右侧选点。 所有区间按照右端点 E E E从小到大排序排序后第i区间范围为 [ B i , E i ] [B_i, E_i] [Bi,Ei]其中需要至少选择 T i T_i Ti个点。 贪心选择的具体解释
如果该区间中已经选择点的数量大于等于 T i T_i Ti则不需要再选点。如果该区间中已经选择点的数量小于 T i T_i Ti则从 E i E_i Ei到 B i B_i Bi从大到小遍历每个点遇到未选择的点就选择该点直到选够 T i T_i Ti个点。 贪心选择性质的证明 证明存在最优解包含第一次的贪心选择 第一次的贪心选择为在 [ B 1 , E 1 ] [B_1,E_1] [B1,E1]中选择区间 [ E 1 − T 1 1 , E 1 ] [E_1-T_11, E_1] [E1−T11,E1]中的整数点共 T 1 T_1 T1个点。 反证法假设所有最优解都不包含第一次的贪心选择 也就是说在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]选择了一些点而 [ E 1 − T 1 1 , E 1 ] [E_1-T_11, E_1] [E1−T11,E1]中存在未被选择的点。设在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]中选择了点 G G G而 [ E 1 − T 1 1 , E 1 ] [E_1-T_11, E_1] [E1−T11,E1]中点 F F F未被选择。 现在不选择点 G G G转而选择点 F F F第2、第3等后面的区间中已选择的点可能会增加也可能不变。每个区间的选点数量都满足要求总选点数量不变。因此这样变换选择点后此时的选点方案仍然是最优解。 将在 [ B 1 , E 1 − T 1 ] [B_1, E_1-T_1] [B1,E1−T1]中选择的所有点都去掉转而在 [ E 1 − T 1 1 , E 1 ] [E_1-T_11, E_1] [E1−T11,E1]中选择相同数量的点最后选择的点就是 [ E 1 − T 1 1 , E 1 ] [E_1-T_11, E_1] [E1−T11,E1]中的每个点这也就是进行了贪心选择这个包含了第一次贪心选择的解仍然是最优解。这与假设相悖原命题得证。假设最优解包含前k次的贪心选择证明存在最优解包含第k1次的贪心选择 证明过程与第1点的证明过程相似不再赘述。 具体实现 设vis数组vis[i]表示第i点是否已被选择。 对于每个区间先遍历整个区间统计出已选点数量也就是求出待选择点的数量。
如果待选择点的数量为0就看下一个区间。否则从区间右端点开始向前遍历遇到未选择的点就选择一个点直到待选择点的数量为0。统计选点总数量就是问题结果。
【题解代码】
解法1贪心
#includebits/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(a1, a1m, 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;
}
