cf #310 D. Case of Fugitive (二分)

题目：http://codeforces.com/contest/556/problem/D

题意：在一条水平线上有n条互不相交的线段，你有m个桥，每个桥的长度已知，桥能搭起来的条件是桥的两个端点分别在两个线段上。现在问你能不能将所有的线段连起来。

分析：对于相邻的两条线段[L1,R1]和[L2,R2],能连起来的条件是，存在一个长为x的桥，L2-R1<=x<=R2-L1。

设相连两个线段的相连的满足区间为[dmin,dmax]，其中dmin=L2-R1，dmax=R2-L1。

那么有n-1个区间需要满足。

将n-1个区间，先按dmax从小到大排序，再按dmin从小到大排序。

排序后，排在前面的区间的优先级高。看下面两张图就知道了。

对于情况1，明显上面的区间优先级高，对于情况2，先找上面的区间突出来的部分。。。。

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1E9+9;
const int maxn = 2e5+6;struct node
{LL first,second;int id;bool operator < (const node &t)const{if(second!=t.second)return second<t.second;return first<t.first;}
}d[maxn];int ans[maxn];
pair <LL,LL> p[maxn];
multiset <pair <LL,LL> > st;int main()
{int i,j,n,m,x,y,px,pu;scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%lld%lld",&p[i].first,&p[i].second);for(i=0;i<m;i++){LL a;scanf("%lld",&a);st.insert(make_pair(a,i+1));}sort(p,p+n);for(i=0;i<n-1;i++){d[i].first=p[i+1].first-p[i].second;d[i].second=p[i+1].second-p[i].first;d[i].id=i+1;}n--;sort(d,d+n);for(i=0;i<n;i++){multiset <pair <LL,LL> >::iterator it = st.lower_bound(make_pair(d[i].first,-1));if(it==st.end() || it->first>d[i].second){puts("No");return 0;}ans[d[i].id]=it->second;st.erase(it);}puts("Yes");for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0;
}