区间问题
贪心问题没有什么固定的套路,有时自己的灵光一现,然后带几个样例进去尝试我们就能验证自己“贪”地合不合理,如果合理大胆尝试就行
题一
这题的题一如下:在数轴中标记最少的点,使得每个区间至少包含一个点
一般情况下,区间问题我们会进行排序,不同的排序方法可以帮助我们做出不同的题目
此题我们使用y总给的图即可(主要是懒得自己画QAQ):
例如此题,我们可以以右端点进行从小到大的排序,排序我们使用stl库就行,只不过数据结构上我们需要自己写一个cmp(我觉得自己写更好掌控排序的结果)
排序完以后我们就会发现一个性质:第一个区间的右端点值与其他区间的左端点值决定了它们是否在同一区间,即:
- 在有交集的区间中,最小的右端点值一定比它们的左端点值大
- 在互相无交集的区间中,上一个最小右端点值一定比它们的左端点值小
我们来证明一下,反证法:
假设在有交集的区间中,最小的右端点值一定比它们的左端点值小
右端点比左端点小,那么它们没有交集,矛盾
假设在互相无交集的区间中,上一个最小右端点值一定比它们的左端点值大
右端点比左端点大,那么它们有交集,矛盾
还有一个,为什么判断点是最小的那个右端点呢?
因为当我们的点是最小的右端点时,我能够保证在这个点上,与我有交集的区间最多,这个读者看上图中的1、2、3号区间就能理解
能用贪心去做的题目一般有这么一个必要条件:可以将问题分成若干个小问题,且各个小问题是独立的,之间没有关系,那么每个子问题的最优解的集合一定就是整个问题的最优解
那么对于此题,我们将区间排序后就能将我们的问题拆分成这样的子问题:寻找能包含最多区间的交集,找到后去掉这几个区间继续寻找下一个,直至没有区间可寻找或寻找最大交集的个数
此时我们找到后就丢到找到的,因为它们都能包含同一个点,那么会不会影响下一次选择呢?并不会,因为我们只关心一个点能最多被几个区间包含,并不关系究竟是哪几个区间,所以如果我们去掉这几个区间后,新的最大值只会小于等于上一个最大。每次都取最大,那总问题就能做到最优解
其实这道题目最优的想法是画一个韦恩图,但是区间一多韦恩图会变得及其复杂QAQ
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
std::vector<std::pair<int, int>> myVec;
int n;
int main()
{
std::cin >> n;
for(int i = 0;i<n;i++)
{
int l, r;
std::cin >> l >> r;
myVec.push_back({ l,r });
}
std::sort(myVec.begin(), myVec.end(), [](auto& l, auto& r) {return l.second < r.second; });
int count = 1;
int lastIndex = myVec[0].second;
for(int i = 1;i<n;i++)
{
int l = myVec[i].first, r = myVec[i].second;
if (lastIndex < l)
{
count++;
lastIndex = r;
}
}
std::cout << count;
}
y总代码,会快两倍,但最大的影响还是输入输出导致的
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
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 ++ ) scanf("%d%d", &range[i].l, &range[i].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;
}
题二
这题与上题的数据集相同,但是我们要求的问题出现了变化,我们求的是最多不相交区间,但是....转念一想,我们题目一求的是什么呢?
用最少的点落在所有区间内
那么如果一个点能落在一个区间集合内,那这个区间集合不就是会相交的吗?那这个区间集合我们是否取一个作为我们在题二中的一个解就可以呢?
相通这个问题,我们就可以 Ctrl + C,Ctrl + V了( XD )
这同时也印证了我在题一中写的题解,一个贪心问题可以被转换为多个互不相关的子问题来求每个问题的最优解,而合成整个题目的最优解。
这里就不贴y总的代码了,贴我自己的就ok力,各位想优化时间的话把输入输出改成C标准就可以
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
std::vector<std::pair<int, int>> myVec;
int n;
int main()
{
std::cin >> n;
for(int i = 0;i<n;i++)
{
int l, r;
std::cin >> l >> r;
myVec.push_back({ l,r });
}
std::sort(myVec.begin(), myVec.end(), [](auto& l, auto& r) {return l.second < r.second; });
int count = 1;
int lastIndex = myVec[0].second;
for(int i = 1;i<n;i++)
{
int l = myVec[i].first, r = myVec[i].second;
if (lastIndex < l)
{
count++;
lastIndex = r;
}
}
std::cout << count;
}