蓝桥杯算法提高VIP-线段和点

题目

题目链接

题解

贪心。

我们第一时间想到的贪心思路肯定是尽量去选覆盖区间多，但很快就会发现肯定不对，那我们要如何考虑呢？

贪心思路为：将区间按右端点从小到大排序，遍历每个区间，找到一个点尽量的大，且要求这个点要在当前区间的右端点的左侧（含左端点），统计这样的点的数量就可以了。当然，这只是概述。

想要找到一个坐标小于等于一个数且尽可能大的点，第一时间想到的就是二分吧，

lower_bound

和

upper_bound

。

upper_bound

是找小于的或者大于的，而

lower_bound

是找小于等于的或者大于等于的，因此我们使用

lower_bound

。

使用

lower_bound( begin,end,num,greater<type>() )

且对点的坐标进行从大到小排序，才能找到小于等于的第一个点（在递减的排序中从左向右找，找到的一个小于等于某个值的数一定是最大的满足小于等于这个值的数）。（详细介绍）

虽然找到了这个点，但这个点并不一定能覆盖当前区间啊，假如这个点要是比当前区间的左端点还小呢，也是覆盖不了的，又或者根本就找不到这个点呢？其实，这两种情况都会导致不存在任何一个点能够覆盖当前区间，即结果输出

-1

。为什么这么说呢？如果我们没有找到这个点，那么很显然不存在比当前区间右端点小的数，也就没法覆盖当前区间；如果我们找到了这个点，但是这个点比当前区间左端点还小，就连最靠近当前区间右端点的点都无法比左端点大，那怎么可能还有其他满足条件且比左端点大的点了啊。因此，两种情况下，均要输出

-1

。

现在当前区间确定了找到的点了，下面枚举到下一个区间了。对于新的当前区间（下面统称为当前区间），我们要判断上一个覆盖上一个区间的点能不能顺便把当前区间也覆盖了，如果能，真是太好了省了个点，什么也不用干，直接去判断下一个区间就行了；如果不能，我们就得一板一眼的按照上面的思路走：“找到一个点尽量的大，且要求这个点要在当前区间的右端点的左侧（含左端点）……”。

如何判断上一个区间找到的点（或者准确的说是继承自上一个区间的点，因为这个点有可能来自上上个区间或者上上上个区间……）是不是可以直接覆盖当前区间呢？不就是判断这个点是不是大于等于当前区间的左端点嘛，因为当前区间的右端点比上一个区间的左端点要大，所以这个点也一定在当前区间的左边，因此只需判断左端点与这个点的大小即可了。若大于等于，说明这个点可以覆盖当前区间，对于这个区间什么都不用操作；反之，我们就要如上操作了。

从上面可以看出，我们的贪心思路并没有必须要对点进行从大到小排序的要求，只是为了方便我们实现我们的贪心思路，为了二分才进行的排序。

这个贪心思路确实不好想，但也属于比较经典的贪心思路了，如果要证明的话我也不会，但是我有一种奇奇怪怪的理解方式，算是这个贪心思路的本质？（bushi）

比如这三段区间，假设是一段区间集合中的三段（并不一定右端点要重合）；

区间按右端点从小到大排序，我们找尽可能大的且小于等于右端点的点，有点类似一个夹逼的感觉（不要ghs），我们让这个点尽量靠近右端点，这样才能让他覆盖尽可能多的区间，当然这时在保证区间按右端点从小到大排序的前提下。

其实这题也可以，将区间按左端点从大到小排序，找尽可能小的且大于等于左端点的点，其实也是一个道理，也是夹逼的感觉，这种夹逼会让点的作用发挥到最大，覆盖尽可能多的区间。

代码1对应“区间按右端点从小到大排序，找尽可能大的且小于等于右端点的点”，也就是上面我们主要将的内容；

代码2对应“区间按左端点从大到小排序，找尽可能小的且大于等于左端点的点”，实现起来几乎一样，就改几个符号啥的，区别不大。

代码1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;

struct B {
	int l, r;
};

int a[N], n, m, ans;
B b[N];

bool cmp1(int x, int y) {
	return x > y;
}

bool cmp2(B x, B y) {
	return x.r < y.r;
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i ++) cin>>a[i];
	for(int i = 1;i <= m;i ++) cin>>b[i].l>>b[i].r;
	sort(a+1, a+n+1, cmp1);
	sort(b+1, b+m+1, cmp2);
	
	int left = -1, flag = 0;
	for(int i = 1;i <= m;i ++) {
		if(left < b[i].l) {
			int t = lower_bound(a+1, a+n+1, b[i].r, greater<int>()) - a;
			if(t == n+1 || a[t] < b[i].l) {flag = 1; break;} // 两种输出-1的情况
			ans ++;
			left = a[t];
		}
	}
	if(!flag) cout << ans;
	else puts("-1");
		
	return 0;
}

           

代码2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;

struct B {
	int l, r;
};

int a[N], n, m, ans;
B b[N];

bool cmp(B x, B y) {
	return x.l > y.l;
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n;i ++) cin>>a[i];
	for(int i = 1;i <= m;i ++) cin>>b[i].l>>b[i].r;
	
	sort(a+1, a+n+1);
	sort(b+1, b+m+1, cmp);
	
	int right = 50005, flag = 0;
	for(int i = 1;i <= m;i ++) {
		if(right > b[i].r) {
			int t = lower_bound(a+1, a+n+1, b[i].l) - a;
			if(t == n+1 || a[t] > b[i].r) {flag = 1; break;}
			ans ++;
			right = a[t];
		}
	}
	if(!flag) cout << ans;
	else puts("-1");
		
	return 0;
}