http://codeforces.com/contest/556/problem/D
给你n个岛和m个桥,岛在一条线上,有左端点l, 和右端点r(r>l),问你能不能用桥把所有岛连在一起
要求:桥要>=两个相邻岛之间最短距离,<=最大距离
有些时候,具体的问题不好思考,比如这题的岛和桥这些具体的东西,我们可以把他们转化成抽象的线和点将有助于我们思考。
由于这题桥只能建在相邻岛之间,又与岛与岛之间最大距离和最小距离有关,我们将这两个数据提取出来,就有一个minL , maxL , 那么桥要能建就必须满足minL <= li <= maxL
因此我们就可以把问题转化为在一条线上有几个区间,线上有几个点,问你点能不能分配到所有区间上,而且每个区间上只能分配一个点(点可以不用完,但是区间必须要有一个点)
我们把记下的maxL , minL 按照maxL的大小从小到大排序,然后根据minLi去二分找桥,如果该桥>maxLi , 那就是no了,否则删了该桥
由于我们是按maxL从小到大排序的,按照minL找最先满足li>=minLi且<=maxL的桥,找到就给他,为什么这个策略是对的,因为如果该桥可以满足多个区间,那么maxL大的还可以找更长的桥,如果把该桥给了maxL大的,那么maxL小的就可能没有符合的桥了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pr;
set<pr>cnt;
const int M = 2e5 + 10;
struct P
{
ll ma, mi, id;
bool operator < (const P& a){
if(ma == a.ma) return mi > a.mi; //如果maxL相等,谁在前面其实无所谓
return ma < a.ma;
}
}p[M];
pr temp[M];
ll ans[M];
int main()
{
memset(p, 0, sizeof(p));
memset(ans, 0, sizeof(ans));
int n, m, top = 0;
scanf("%d%d", &n, &m);
for(int i=0; i<n; ++i){
ll l, r;
scanf("%lld%lld", &l, &r);
temp[i] = pr(l, r);
}
for(int i=1; i<=m; ++i){
ll len;
scanf("%lld", &len);
cnt.insert(pr(len, i));
}
for(int i=1; i<n; ++i){
p[top++] = P{temp[i].second - temp[i - 1].first, temp[i].first - temp[i - 1].second, i-1};
}
sort(p, p+top);
int i;
for(i=0; i<n-1; ++i){
set<pr>::iterator it;
it = cnt.lower_bound(pr(p[i].mi, 0));
if(it == cnt.end() || (it->first) > p[i].ma)
break;
else{
ans[p[i].id] = it->second;
cnt.erase(it);
}
}
if(i != n-1) puts("No");
else{
puts("Yes");
for(int i=0; i<n-1; ++i)
cout<<ans[i]<<' ';
}
cout<<endl;
return 0;
}