链接

题目大意：n个岛屿，在一条线上，岛屿有起点和终点，有m座桥，问能不能用n-1座桥把岛屿连起来

题目思路：

1. 根据岛屿信息，我们将 n−1 个需要的区间拿出来，试着用给我们的桥长度去覆盖这些区间。
2. 问题转化为了给一些区间和一些点，一个点最多覆盖一个区间，询问这些点能否将区间全覆盖。（桥的长度值就是点坐标，一共m个点；相邻岛屿间距范围就是一个区间，区间左端点坐标值为相邻岛屿最小距离，区间右端点坐标值为相邻岛屿最大距离，一共n-1个区间）
3. 按照一般的贪心套路，将所有区间按照左端点排序，点也排序。每一次点覆盖我们右端点最靠左的区间。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 200001;
struct Island{
    long long left;  // 岛屿左端点
    long long right;  // 岛屿右端点
};
struct Bridge{
    long long length;  // 桥的长度
    long long index;  // 桥的编号
};
struct Interval{
    long long minimum;   // 区间最小值
    long long maxmum;   // 区间最大值
    long long index;  // 区间编号
    bool operator< (Interval x) const{   // 这样在优先队列中，就能从小到大排序
        return maxmum > x.maxmum;
    }
};
bool IntervalCompare(Interval x, Interval y){
    if(x.minimum == y.minimum) return x.maxmum<y.maxmum;
    return x.minimum<y.minimum;
}
bool BridgeCompare(Bridge x, Bridge y){
    return x.length<y.length;
}
Island island[MAXN];
Bridge bridge[MAXN];
Interval interval[MAXN];
long long answer[MAXN];
bool Solve(int n, int m){
    priority_queue<Interval> myQueue;   // 在priority_queue中，优先队列默认是大顶堆.   从大到小排序的
    int position = 0;  // 当前区间下标
    int number = 0;  // 搭建桥的数目
    for(int i=0;i<m;i++){  // 遍历每个桥
        while(!myQueue.empty() && myQueue.top().maxmum < bridge[i].length){
            myQueue.pop();    // 当前区域无法搭建
        }
        while(position < n-1 &&
              interval[position].minimum <= bridge[i].length &&
              interval[position].maxmum >= bridge[i].length){    // 当前区域能够搭建
            myQueue.push(interval[position]);
            position++;
        }
        if(!myQueue.empty()){  // 用桥进行搭建
            Interval current = myQueue.top();
            myQueue.pop();
            answer[current.index] = bridge[i].index;
            number++;
        }
    }
    return number == n-1;  // 判断桥数与区间数是否相等
}
int main(){
    int n,m;
    while(scanf("%d%d", &n, &m)!=EOF){
        memset(island,0,sizeof(island));
        memset(bridge,0,sizeof(bridge));
        memset(interval,0,sizeof(interval));
        memset(answer,0,sizeof(answer));
        for(int i=0;i<n;i++){
            scanf("%I64d%I64d",&island[i].left,&island[i].right);
        }
        for(int i=0;i<m;i++){
            scanf("%I64d",&bridge[i].length);
            bridge[i].index = i+1;
        }
        for(int i=0;i<n-1;i++){
            interval[i].minimum = island[i+1].left - island[i].right;
            interval[i].maxmum = island[i+1].right - island[i].left;
            interval[i].index = i;
        }
        sort(interval,interval+n-1,IntervalCompare);
        sort(bridge,bridge+m,BridgeCompare);
        if(Solve(n,m)){
            printf("Yes\n");
            for(int i=0;i<n-1;i++){
                printf("%I64d\n",answer[i]);
            }
        }else{
            printf("No\n");
        }
    }
    return 0;
}