藍橋杯算法提高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;
}