Codeforces 555B - Case of Fugitive 搭桥
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Codeforces 555B - Case of Fugitive 搭桥，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3305字，纯文字阅读大概需要5分钟。
内容图文
题意：给出n段路和m座桥。每段路的两个端点一维坐标表示。要从m座桥中选出一些桥搭在每两条相邻的路上，使得这些路全部连通。每两条相邻的路之间只能搭一座桥，且桥的两端必须恰好分别落在两段路上。如果存在一种搭桥方法，则输出Yes并按题目给定的路形成的空隙的顺序输出每座桥的序号，若不能则输出No。
题意换个说法实际上就是给定n - 1个区间和m个数，问是否能从m个数中选出n - 1个数，恰好分别落在n - 1个区间内。
觉得可以用贪心做，开始想了下因为区间有两个端点，而且位置任意，有点不好处理。后来就想先以一个端点排序，以另一个端点作为贪心准则。首先对于所有的区间，我们按右端点递增排序。左端点不予考虑。并将所有的数（即桥长）递增排序。然后依次遍历每个区间，然后从剩下的数中找最小的可以满足这个区间的数去满足这个区间，如果找不到则直接输出No。下面我们证明这个思路的正确性。用数学归纳法即可证明。
对于第一个区间[L1，R1]，若有某两个数都能满足这个区间，设较小的数为min，较大的数为max，如果我们用max去满足这个区间的话：
1、若最后的解中min没有被用来满足任何区间，那么我们将max换为min，不影响结果，因此我们可以使用min去满足这个区间。
2、若最后的解中min满足了某个其他的区间 [L2，R2]，则 [L2，R2] 必定排序在 [L1，R1] 的后面（因为 [L1，R1] 是第一个区间），故有R2 ≥ R1，L2 ≤ min ≤ R2。因为min也同时满足 [L1，R1]，所以必有L2 ≤ R1。由max在 [L1，R1] 区间可知max ≤ R1。故有L2 ≤ min ≤ max ≤ R1 ≤ R2，即L2 ≤ max ≤ R2，也就是max同时也满足 [L2，R2] 区间。因此这个两个数分别同时满足这两个区间。我们将它们互换，并不影响结果，同样可以使得min去满足 [L1，R1]这个区间。
假如我们按上述方法满足了前k个区间。那么对于第k + 1个区间[L1，R1]，若还是有两个数（这两个数暂时均未被用来满足任何区间）能满足此区间，仍设较小的数为min，较大的数为max，如果我们用max去满足这个区间的话：
1、若最后的解中min没有被用来满足任何区间，那么我们将max换为min，不影响结果，因此我们可以使用min去满足这个区间。
2、若最后的解中min满足了某个其他的区间 [L2，R2]，若 [L2，R2] 排序在 [L1，R1] 之前，那么我们会在先前选择满足 [L2，R2] 这个区间的数时，就将这个数用来满足 [L2，R2] 区间了，于是在选择满足当前区间 [L1，R1] 的数时，min已经被满足于先前的区间（即 [L2，R2]）。矛盾。因此 [L2，R2] 必定排序在 [L1，R1] 的后面。这样的话，按照刚才的分析，仍可以用min去满足 [L1，R1]这个区间。
故这样的贪心准则是可行的。对于每个区间要从剩下的数中找最小的满足区间的数可以二分，但是二分之后要删去这个数（因为后面不再用到）所以这里用mult_set实现。
/*----------------------
虽然是第一次打div1。。。。。
然而并不想打div1。。。。。
但是rating涨上去了又不得不打div1。。。。。
然而打了又不得不掉rating下次继续打div2。。。。。
好纠结啊。。。。。
以后只要再被逼无奈打div1。。。。。
我一定像这次一样坐等掉rating然后去打div2。。。。。
I LOVE AC
AC_FirstLucker
----------------------*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct Bridge //桥
{
int id;
long long lenth;
};
struct Range //区间
{
int id;
long long l;
long long r;
};
const int MAX = 200005;
int n, m;
Range range[MAX];
Bridge temp[MAX]; //先用数组排序后再插入到集合中
multiset <Bridge> bridge;
bool operator < (Range r1, Range r2)
{
return r1.r < r2.r;
}
bool operator < (Bridge b1, Bridge b2)
{
return b1.lenth < b2.lenth;
}
void input()
{
long long x, y, tx, ty;
scanf("%I64d%I64d", &tx, &ty);
for(int i = 0; i < n - 1; i++)
{
scanf("%I64d%I64d", &x, &y);
range[i].id = i;
range[i].l = x - ty;
range[i].r = y - tx;
tx = x;
ty = y;
}
for(int i = 0; i < m; i++)
{
scanf("%I64d", &temp[i].lenth);
temp[i].id = i;
}
}
void solve()
{
int ans[MAX]; //记录答案
sort(range, range + n - 1);
sort(temp, temp + m);
bridge.clear();
for(int i = 0; i < m; i++)
bridge.insert(temp[i]);
for(int i = 0; i < n - 1; i++)
{
Bridge value;
value.lenth = range[i].l;
set <Bridge>::iterator it = bridge.lower_bound(value);
if((*it).lenth < range[i].l || (*it).lenth > range[i].r) //找不到任何可以满足当前区间的桥
{
printf("No\n");
return;
}
ans[range[i].id] = (*it).id; //用找到的桥满足这个区间
bridge.erase(it); //删除当前找到的桥
}
printf("Yes\n");
for(int i = 0; i < n - 1; i++)
{
if(i > 0)
printf(" ");
printf("%d", ans[i] + 1);
}
printf("\n");
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
input();
solve();
}
return 0;
}
??
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/firstlucker/article/details/46685483
内容总结
以上是互联网集市为您收集整理的Codeforces 555B - Case of Fugitive 搭桥全部内容，希望文章能够帮你解决Codeforces 555B - Case of Fugitive 搭桥所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。