Codeforces 555B Case of Fugitive 排序+贪心

题意：

有n个岛屿放在同一个条线上，并且把每个岛的左右端点给你。

然后有m条桥，每条桥都有一定的长度。现在让你把桥放在相邻两个岛之间，使得它们能够连通（桥的两端要落在两个岛屿上）。

现在问你，是否存在合法方案，存在则输出方案。不存在则输出"No".

思路：

首先对于两两相邻的岛屿，根据端点值，我们可以处理出n-1个可放桥的长度区间。

然后对于n-1个区间，根据l值进行升序排序。

再对桥的长度len进行升序排序，用桥来选择区间。

在选择区间过程中，我们只要选择l<=len，r >= len中，r最小的那个作为当前桥所选的区间。

因为对于l <= len的区间，只有r的区别，将两个影响因素转变成一个，然后贪心选择r最小的。

实现中我用set来维护一组l<=len的区间，然后每次取set.begin（）。

code：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
typedef long long LL;
int n, m;
struct Seg {
LL l, r;
int id;
bool operator < (const Seg& cmp) const {
return l < cmp.l;
}
}a[N], c[N];
struct Len {
LL val;
int id;
bool operator < (const Len& cmp) const {
if(val == cmp.val) return id < cmp.id;
return val < cmp.val;
}
}b[N];
set <Len> st;
int res[N];
bool solve() {
int tn = 0;
for(int i = 1;i < n; i++) {
c[tn].l = a[i].l-a[i-1].r;
c[tn].r = a[i].r-a[i-1].l;
c[tn].id = tn;
tn++;
}
sort(c, c+tn);
sort(b, b+m);
for(int i = 0, j = 0;i < m; i++) {
while(!st.empty() && ((st.begin()->val) < b[i].val))
st.erase(st.begin());
while(j < tn && c[j].l <= b[i].val && c[j].r >= b[i].val) {
st.insert((Len){c[j].r, c[j].id});
j++;
}
if(st.empty()) continue;
auto it = st.begin();
res[it->id] = b[i].id+1;
st.erase(it);
}
for(int i = 0;i < tn; i++)
if(res[i] == 0) return false;
return true;
}
int main() {
scanf("%d%d", &n, &m);
//ios::sync_with_stdio(false);
for(int i = 0;i < n; i++)
scanf("%I64d%I64d", &a[i].l, &a[i].r);
for(int i = 0;i < m; i++) {
scanf("%I64d", &b[i].val);
b[i].id = i;
}
if(solve()) {
puts("Yes");
for(int i = 0;i < n-1; i++)
printf("%d ", res[i]);
puts("");
}
else
puts("No");
return 0;
}

最后

以上就是现代树叶为你收集整理的Codeforces 555B Case of Fugitive 排序+贪心的全部内容，希望文章能够帮你解决Codeforces 555B Case of Fugitive 排序+贪心所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。