[CF310]D. Case of Fugitive

题意： 给出n个线段，在n个线段之间搭桥，给出m个桥的长度，假如满足条件 To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i-th and the (i+1)-th islads, if there are such coordinates of x and y, that li≤x≤ri, li+1≤y≤ri+1 and y-x=a. ，问最后可以连接所有的线段吗？是的话输出线段所对应的桥的编号。

分析： 数据量比较大，，虽然题意很简单，但是要想一些办法降低复杂度。这个数据量二分可以nlogn可以处理，那这里就用了set来处理，二分就用了lower_bound，另外题一点，pair

;set <pair<pair<LL,LL>, int> > s;multiset<pair<LL,LL> > k;int res[maxn];int main(){ //’std::set<std::pair<std::pair<long long int, long long int>, int> >::iterator’ has no member named ‘first’LL n,m,x,y,a,b;int i,j;std::ios::sync_with_stdio(false);cin>>n>>m;for(i=0;i<n;i++){cin>>x>>y;if(i>0)s.insert(make_pair(make_pair(y-a,x-b),i));a=x;b=y;}for(i=1;i<=m;i++){cin>>x;k.insert(make_pair(x,i));}for(set<pair<pair<LL,LL>, int> >:: iterator it =s.begin();it!=s.end();it++){multiset<pair<LL,LL> > :: iterator j=k.lower_bound(make_pair(it->first.second,-1));if(j==k.end() || j->first>it->first.first){cout<<“No”<<endl;return 0;}res[it->second]=j->second;k.erase(j);}cout<<“Yes”<<endl;for(i=1;i<n;i++)cout<<res[i]<<” “;cout<<endl;}

ps:觉得对STL不熟。。。

当你感到悲哀痛苦时，最好是去学些什么东西。