Codeforces555 B.Case of Fugitive（贪心+set）

题意：

如果能联通，输出连接方案。

数据范围：n,m<=2e5，1<=l,r,a(i)<=1e18

解法：

假设相邻区间为[l1,r1],[l2,r2],
那么能连接他们的木板长度应该在范围[l2-r1,r2-l1]内.
这样的话就有n-1个形如(l,r)的二元组.
将二元组按照r从小到大排序,r相同时按照l从小到大排序.
因为排序之后r是递增的,r相同时l是递增的,
那么遍历二元组(l,r)时,应该贪心地找在[l,r]范围内的最短木板.
木板可以用set存,找木板在set里面二分就行了.

code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=2e5+5;
struct Line{int l,r,id;
}xx[maxm];
int l[maxm],r[maxm];
int ans[maxm];
int n,m;
bool cmp(Line a,Line b){if(a.r!=b.r)return a.r<b.r;return a.l<b.l;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;//for(int i=1;i<=n;i++){cin>>l[i]>>r[i];}for(int i=1;i<=n-1;i++){xx[i]={l[i+1]-r[i],r[i+1]-l[i],i};}sort(xx+1,xx+1+(n-1),cmp);//multiset<PI>s;for(int i=1;i<=m;i++){int x;cin>>x;s.insert({x,i});}//for(int i=1;i<=n-1;i++){auto it=s.lower_bound({xx[i].l,0});//找>=l的最小的if(it==s.end()||it->first>xx[i].r){cout<<"No"<<endl;return 0;}ans[xx[i].id]=it->second;s.erase(it);}cout<<"Yes"<<endl;for(int i=1;i<=n-1;i++){cout<<ans[i]<<' ';}cout<<endl;return 0;
}