【贪心】CodeForces：556D Case of Fugitive

一、题目内容

CodeForces：556D Case of Fugitive 原题地址

二、题意解释

有N个岛屿，每个岛屿的左端点和右端点已知，此时有m种桥，其长度已知，问能否用这些桥连接起来所有的岛屿。

三、代码及注释

#include<stdio.h> #include<algorithm> #include<queue> using namespace std; typedef long long ll; //思想：把桥长和岛屿所得区间长的小值都先升序排列，接着对每个桥长， //考虑是否有合适的区间（区间小值<桥长<区间大值），如有，则取区间大值最小的那一个（这里使用了优先队列） int n,m; //岛屿 struct N { ll x,y; } node[200005]; //区间 struct F { ll mi,ma; int idx; bool used; //按照小值排序 bool operator < (const F &A) const { return mi<A.mi; } } fanwei[200005]; //桥 struct Bridge { ll len; int idx; bool operator < (const Bridge &A) const { return len<A.len; } } bridge[200005]; //按照区间大值重载优先队列排序函数 struct cmp { bool operator()(const int a,const int b) { return fanwei[a].ma>fanwei[b].ma; } }; int ans[200005]; int main() { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { scanf("%lld%lld",&node[i].x,&node[i].y); } for(int i=0; i<m; i++) { scanf("%lld",&bridge[i].len); bridge[i].idx=i+1; } for(int i=0; i<n-1; i++) { fanwei[i].mi=node[i+1].x-node[i].y; fanwei[i].ma=node[i+1].y-node[i].x; fanwei[i].idx=i; fanwei[i].used=false; } //排序 sort(bridge,bridge+m); sort(fanwei,fanwei+n-1); int size=0; priority_queue<int,vector<int>,cmp> Q;//定义优先队列，并重载排序函数 for(int i=0;i<m;i++){ for(int j=0;j<n-1&&fanwei[j].mi<=bridge[i].len;j++){//找到符合区间小值<桥长的区间，生成优先队列 Q.push(j); } //找到优先队列中最小的区间大值，且该大值需要大于等于桥长 while(!Q.empty()){ int tmp=Q.top(); Q.pop(); if(fanwei[tmp].ma>=bridge[i].len&&fanwei[tmp].used==false){ ans[fanwei[tmp].idx]=bridge[i].idx; fanwei[tmp].used=true; size++; break; } } } if(size!=n-1) { printf("No\n"); } else if(size==n-1) { printf("Yes\n"); for(int i=0; i<size-1; i++) { printf("%d ",ans[i]); } printf("%d\n",ans[size-1]); } return 0; }