CF555B（贪心+二分）

题目链接：http://codeforces.com/problemset/problem/555/B

题意是有一些岛，按顺序给出他们的左极点和右极点，要求在相邻的岛之间建桥，桥的长度必须在岛的范围内，现在给你m条桥，问你能不能满足建造要求，同时输出分配方案。

数据范围在2E5，所以复杂度应该是NlogN……那就二分+贪心搞搞……先按照区间的r排序，然后按照l排序，每次二分最小的满足的桥分配给它就好了……

我我一开始先对l排序再对r排序，这样很容易能举出反例…我真是傻逼……然后又无限TLE，后来qwb菊苣告诉我vecotr的erase是O(N)的……改成mutiset就过了……

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define PB push_back
#define UB upper_bound
#define LB lower_bound
#define MP make_pair
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<vi>
#define mst(x,y) memset(x,y,sizeof(x))
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define sp system("pause")
#define INF 1e18
#define MAXN 50005
#define hash hhash
#define PI acos(-1.0)
#define eps 1e-4

struct node
{
    int id;
    ll l,r;
}p[200005];

bool cmp(node a, node b)
{
    if(a.r != b.r)
        return a.r < b.r;
    return a.l > b.l;
}

pair<ll,ll> pp[200005];
ll sv[200005];

int main()
{
    int n,m;
    cin >> n >> m;
    ll a,b;
    cin >> a >> b;
    for(int i = 1;i < n;i++)
    {
        ll c,d;
        scanf("%lld %lld",&c,&d);
        p[i].l = c - b,p[i].r = d - a,p[i].id = i;
        //cout << p[i].l << " " << p[i].r << endl;
        a = c,b = d; 
    }
    sort(p + 1,p + n,cmp);

    multiset<pair<ll,int>>v;
    for(int i = 0;i < m;i++)
    {
        cin >> a;
        v.insert(MP(a,i));
    }
    int ok = 1;
    for(int i = 1;i < n;i++)
    {
        multiset<pair<ll,int>>:: iterator it = v.lower_bound(MP(p[i].l,0));
        if(it == v.end() || it -> first > p[i].r)
        {
            ok = 0;break;
        }
        else
            sv[p[i].id] = it -> second + 1,v.erase(it);
    }
    if(!ok)
        cout << "No\n";
    else
    {
        cout << "Yes\n";
        for(int i = 1;i < n;i++)
        {
            printf("%lld ",sv[i]);
        }
    }
}