题目来源： CodeForces
基准时间限制：1.5 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
收藏
关注
li+1 对于所有的 1 ≤ i ≤ n-1。现在要将相邻的小岛用桥连接起来。现在有一条桥的长度是a，第i个岛和第i+1个岛能够连接的条件是，存在x,y使得 li ≤ x ≤ ri, li+1 ≤ y ≤ ri+1
现在有m条桥，每条桥最多被使用一次，问能否把这些岛连接起来。
样例解释：在这个样例中，把第2条桥两个端点放在3和8，把第三条桥两个端点放在7和10，把第一条桥的端点放在10和14。
Input
单组测试数据。第一行有两个整数n (2 ≤ n ≤ 2*10^5) 和 m (1 ≤ m ≤ 2*10^5)，表示岛的数目和桥的数目。接下来n行，每行有两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 10^18)，表示岛的两个端点。接下来一行有m个整数 a1, a2, ..., am (1 ≤ ai ≤ 10^18)，表示每一条桥的长度。
Output
如果能够将n座岛连接起来输出YES，否则输出NO。
Input示例
4 41 47 89 10 12 14 4 5 3 8
Output示例
YES
对输入的相邻的两个岛屿,l1, r1, l2,r2生成一个线段[l2-r1, r2-l1]因为有n个岛屿，所以有n-1个线段.先再就是为每个线段配一座桥.
把线段按照右端点从小到达排序，从小到大遍历每个线段l, r, 找到一座桥，其长度>= l && <= r, 并且离l最近，那么就是这个线段的桥
#include <bits/stdc++.h>
#define MOD 1000000007
#define maxn 200005
using namespace std;
typedef long long ll;
struct Node{
Node(){
}
Node(ll a, ll b){
l = a;
r = b;
}
friend bool operator < (const Node&a, const Node&b){
return a.r < b.r;
}
ll l, r;
}node[maxn];
multiset<ll> s;
int main(){
//freopen("in.txt", "r", stdin);
int n, m;
ll x1, y1, x2, y2;
scanf("%d%d", &n, &m);
scanf("%I64d%I64d", &x1, &y1);
for(int i = 0; i < n-1; i++){
scanf("%I64d%I64d", &x2, &y2);
node[i] = Node(x2-y1, y2-x1);
x1 = x2;
y1 = y2;
}
sort(node, node+n-1);
for(int i = 0; i < m; i++){
scanf("%I64d", &x1);
s.insert(x1);
}
multiset<ll> ::iterator iter;
for(int i = 0; i < n - 1; i++){
if(s.empty()){
puts("NO");
return 0;
}
iter = s.lower_bound(node[i].l);
if(iter == s.end() || *iter > node[i].r){
puts("NO");
return 0;
}
s.erase(iter);
}
puts("YES");
return 0;
}