题解 | #CodeForces 555B Case of Fugitive#

• 区间贪心

  踩了很多坑，才想清楚其中的逻辑问题

  思路：计算相邻岛屿可架桥区间长度，升序排列区间长度、桥长，从小到大，寻找满足当前

  桥长的最大长度最小的区间匹配，给后续留下更大的区间匹配范围

• 为什么要根据桥长来遍历区间？

  如果根据区间来查找桥，选最长的桥长匹配，显然导致后续可能较长的区间无法匹配

  而选最短的桥长匹配，若区间的最大长度恰好是降序的，也会导致后续无法匹配（见下图）

  所以只能根据桥长，来寻找合适的区间（优先匹配较小最大长度的），保证足够贪心

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=200010;//数组最大容量

struct range{//建桥的范围（区间）
    long long mi,ma;//mi：最小长度、ma：最大长度
    int index;//索引
    bool operator<(range x)const{//'<'重载:保证优先队列中top是最大长度较小的
      return ma>x.ma;
    }
};

bool comrange(range x,range y){//按最小长度升序（区间）
    if(x.mi==y.mi)return x.ma<y.ma;//可删掉
    else return x.mi<y.mi;
}

struct bridge{//桥
    long long lenth;//长度
    int index;//索引
};

bool combridge(bridge x,bridge y){//按长度升序（区间）
    return x.lenth<y.lenth;
}

range s[maxn];
bridge b[maxn];
int ans[maxn];//输出数组
long long lefts[maxn],rights[maxn];//输入岛屿边界端点
priority_queue<range>myqueue;//优先队列
 
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&lefts[i],&rights[i]);
        }
        for(int i=0;i<m;i++){
            scanf("%lld",&b[i].lenth);
            b[i].index=i;
        }
        for(int i=0;i<n-1;i++){//计算区间
            s[i].mi=lefts[i+1]-rights[i];
            s[i].ma=rights[i+1]-lefts[i];
            s[i].index=i;
        }
    
    sort(s,s+n-1,comrange);
    sort(b,b+m,combridge);
    
    int num=0;//建桥数量
    int i=0;//区间位置
    for(int j=0;j<m;j++){//遍历所有桥
       while(!myqueue.empty()&&myqueue.top().ma<b[j].lenth){//不满足条件的区间出队列
         myqueue.pop();
       }
       while(i<n-1&&s[i].mi<=b[j].lenth&&s[i].ma>=b[j].lenth){//满足条件的区间入队列
         myqueue.push(s[i]);
         i++;
       }
       if(!myqueue.empty()){//选择区间最大长度较小的建桥
         ans[myqueue.top().index]=b[j].index+1;
         myqueue.pop();
         num++;
      }
    }
    if(num!=n-1)printf("No\n");
        else {
                printf("Yes\n");
                for(int i=0;i<n-1;i++){
                    printf("%d ",ans[i]);
                }
                printf("\n");
            }
    }
    return 0;
}
 

原题链接