本文主要是介绍Codeforces Round #310 (Div. 1) B. Case of Fugitive(贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/555/problem/B
题目大意：有n个岛m座桥，要求相邻两个岛之间选择一个桥，桥的长度大于等于两个岛之间的距离，小于等于两个岛两端之间的距离，输出一种可行解，如果不行输出no
题目思路：直接贪心，先按照两个岛之间的距离从大到小，然后选出一个符合要求的最大的桥，如果找不到了就no，否则继续。
贪心策略的合理性在于，当我们为间距最大的岛选择了他能用的最大的桥，下一个岛的间距只能小于等于现在这个岛，如果下一个岛两端之间的距离小于当前岛，那刚才用的桥它要么用不了，要么上一个岛能用的桥它都能用（只要不是太长），如果它凉了上一个也得凉。如果大于当前岛，那也没必要来抢这根，也是凉了上面也得凉。
以下是代码：
#include<bits/stdc++.h>using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 2e5+5;
ll n,m;
ll l[MAXN],r[MAXN];
struct node{ll cha,len,ans,pos;
}c[MAXN];
ll a[MAXN];
bool cmp(node a,node b){if(a.cha==b.cha)return a.len>b.len;return a.cha>b.cha;
}
bool cmp2(node a,node b){return a.pos<b.pos;
}
set<pair<ll,ll> >s;
int main()
{while(~scanf("%I64d%I64d",&n,&m)){s.clear();set<pair<ll,ll> >::iterator it;rep(i,1,n){scanf("%I64d%I64d",&l[i],&r[i]);}rep(i,1,m)scanf("%I64d",&a[i]),s.insert(make_pair(a[i],i));rep(i,1,n-1){c[i].cha=l[i+1]-r[i];c[i].len=r[i+1]-l[i];c[i].pos=i;}sort(c+1,c+n,cmp);ll flag=0;rep(i,1,n-1){it=s.upper_bound(make_pair(c[i].len,2e6));if(it==s.begin()){flag=1;break;}it--;if((*it).first<c[i].cha){flag=1;break;}c[i].ans=(*it).second;s.erase(it);}sort(c+1,c+n,cmp2);if(flag)puts("No");else{puts("Yes");rep(i,1,n-1){printf("%I64d%c",c[i].ans,i==n-1?'\n':' ');}}}return 0;
}
这篇关于Codeforces Round #310 (Div. 1) B. Case of Fugitive(贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
