——以“今年暑假不AC 和 打扫牛棚”为例
这类线段覆盖问题求最大最小值大同小异
今年暑假不AC
题目描述
“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”
确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。 作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）
输入格式
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数\(n(n<=100)\)，表示你喜欢看的节目的总数，然后是\(n\)行数据，每行包括两个数据\(Ti_s,Ti_e\) \((1<=i<=n)\)，分别表示第\(i\)个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。\(n=0\)表示输入结束，不做处理。
输出格式
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行
题目分析
先化解题意（这题B话属实多）
有\(n\)个线段，分别给定长度。要求最多能在其中选取多少条使得他们不首尾覆盖地排列
注意：\([1,i]与[i,j]\)相互之间不覆盖
那么这就是到贪心算法的用武之地了，贪心算法的核心是要去作出当前情况下所能作出的最“贪”的选择，而不用考虑之后的影响。说白了，就是你面前有一张10块和一张100。那肯定是拿那张100的，至于那张10块的，谁去拿，他够不够都不在我们的考虑范围之内。
就这一题而言，我现在肯定优先选择我当前情况下，所能选取的（开始时间肯定要大于等于我上个节目的结束时间），结束时间最早的节目去看。
那么，代码就顺理成章了
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2020-01-21 13:17:11
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
struct $
{
int st;
int en;
};
$ cls[1000005];
bool comp($ a, $ b)
{
if (a.en != b.en)
{
return a.en < b.en;
}
else
{
return a.st < b.st;
}
}
int main()
{
int n;
while (cin >> n, n != 0)
{
memset(cls, 0, sizeof(cls));
for (int i = 0; i < n; i++)
{
cin >> cls[i].st >> cls[i].en;//读取
}
sort(cls, cls + n, comp);//按照结束时间优先排序，将结束的早的放在前面
int cur_end = 0;//记录我当前的结束时间
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (cls[i].st >= cur_end)//这个可以选取
{
cur_end = cls[i].en;//更新结束时间
++cnt;
}
}
cout << cnt << endl;
}
return 0;
}
打扫牛棚
题目描述
大表哥分配 N \((1 <= N <= 25000)\) 只中的一些奶牛在牛棚附近做些清洁。 他总是要让至少一只牛做清洁。他把一天分成T段\((1 <= T <= 1000000)\), 第一段是\(1\)，最后一段是\(T\)
每只奶牛只在一些时间段有空。奶牛如果选择某一段时间，则必须完成整段时间的工作
你的任务是帮助他安排一些奶牛，使每段时间至少有一只奶牛被安排来做这件事。并且奶牛数应尽可能小。如果不可能办到，输出\(-1\)
输入格式
* 第一行：\(N\)和\(T\)
* 第二行至\(N+1\)行: 每一行包括奶牛能工作的开始和结束时间。闭区间。
输出格式
每组数据一行，输出完成清洁所需最少的奶牛数，如果不可能办到，输出\(-1\)
题目分析
首先把题目翻译成人话
有一段从\(1\)到\(n\)的区间，现有多条线段(左右界不同，有重合区域)，求最少需几条线段才能覆盖整个大区间？
并且根据这个题目的描述。这样的两个区间如\([1, 3]\) , \([4, 7]\)也算覆盖了\([1,7]\)
既然要达到一个最短覆盖数的效果，那么贪心策略也是比较显然的，我们肯定是要优先去选择更长的线段（直观来看）。说成比较严谨的语言，就是我要选取当前能够选取的所有情况中，结束点最大的那一条线段。
这样的实现也并不复杂，我们还是和上一条一样，利用一个cur_end变量去记录当前的结束位置即可。
需要注意的几个情况主要有出现间断点的情况，这个及时break
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2020-02-07 13:17:49
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct $ //结构体存储每一个奶牛的开始时间和结束时间
{
int s;
int e;
};
$ cow[25005];
bool cmp($ a, $ b)
{
if (a.s != b.s)
{
return a.s < b.s;
}
else
{
return a.e > b.e;
}
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
int n, t;
scanf("%d %d", &n, &t);
for (int i = 0; i < n; i++)
{
scanf("%d %d", &cow[i].s, &cow[i].e);
}
//每一次都优先选择起始点比最大，结束时间最大
sort(cow, cow + n, cmp); //优先按照开始时间排序，当开始时间相同时优先排结束时间最晚的
int cur_end = 0;
int cur_end_max = 0;
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (cow[i].s <= cur_end + 1) //遍历所有的能够选取的情况
{
cur_end_max = max(cow[i].e, cur_end_max); //选取最大值
if (cur_end_max >= t)
{
++cnt;
break;
}
}
else //已经把所有当前能够选取的情况遍历过了，需要更新情况
{
if (cur_end == cur_end_max) //没有得到任何变化直接break也就是说我到这个位置就已经结束位置就增加不上去了(或者说是存在了间断)
{
break;
}
cur_end = cur_end_max; //更新当前的结束位置
cur_end_max = 0;
++cnt; //计数+1
--i; //重新从当前这个点开始遍历
}
}
if (cur_end_max < t)
{
cout << "-1" << endl;
}
else
{
cout << cnt << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
说在最后，这两条题目一条求最大一条求最小，读者们不妨互相对照印证