首页 > 试题广场 >

CodeForces 555B Case of Fugiti

[编程题]CodeForces 555B Case of Fugiti

热度指数：11 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Andrewid the Android is a galaxy-famous detective. He is now chasing a criminal hiding on the planet Oxa-5, the planet almost fully covered with water.

The only dry land there is an archipelago of n narrow islands located in a row. For more comfort let's represent them as non-intersecting segments on a straight line: island i has coordinates [l _i, r _i], besides, r _i < l _i + 1 for 1 ≤ i ≤ n - 1.

To reach the goal, Andrewid needs to place a bridge between each pair of adjacent islands. A bridge of length a can be placed between the i -th and the (i + 1)-th islads, if there are such coordinates of x and y , that l _i ≤ x ≤ r _i , l _i + 1 ≤ y ≤ r _i + 1 and y - x = a .

The detective was supplied with m bridges, each bridge can be used at most once. Help him determine whether the bridges he got are enough to connect each pair of adjacent islands.

输入描述:

The first line contains integers n (2 ≤ n ≤ 2·10⁵) and m (1 ≤ m ≤ 2·10⁵) — the number of islands and bridges.

Next n lines each contain two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10¹⁸) — the coordinates of the island endpoints.

The last line contains minteger numbers a₁, a₂, ..., a_m (1 ≤ a_i ≤ 10¹⁸) — the lengths of the bridges that Andrewid got.

输出描述:

If it is impossible to place a bridge between each pair of adjacent islands in the required manner, print on a single line "No" (without the quotes), otherwise print in the first line "Yes" (without the quotes), and in the second line print n - 1 numbers b₁, b₂, ..., b_n - 1, which mean that between islands i and i + 1 there must be used a bridge number b_i.

If there are multiple correct answers, print any of them. Note that in this problem it is necessary to print "Yes" and "No" in correct case.

示例1

输入

4 4<br />1 4<br />7 8<br />9 10<br />12 14<br />4 5 3 8<br />2 2<br />11 14<br />17 18<br />2 9<br />2 1<br />1 1<br />1000000000000000000 1000000000000000000<br />999999999999999999<br />

输出

Yes<br />2 3 1 <br />No<br />Yes<br />1 <br />

备注:

In the first sample test you can, for example, place the second bridge between points 3 and 8, place the third bridge between points 7 and 10 and place the first bridge between points 10 and 14.

In the second sample test the first bridge is too short and the second bridge is too long, so the solution doesn't exist.

算法知识视频讲解

C/C++

还是想躺平的加菲猫很爱吃鱼

#include<iostream>
(720)#include<cstdio>
#include<algorithm>
(831)#include<vector>
#include<cstring>

using namespace std;

const int MAXN = 2e5 + 20;

struct island {
	long long left;
	long long right;
};

struct bridge {
	long long length, number;
	bool isUsed;							//false表示尚未被使用，true表示已被使用
};

struct dis{
	long long min;
	long long max;
	int num;
	bool isOK;
};

island isl[MAXN];
bridge b[MAXN];
dis d[MAXN];

bool BCompare(bridge a, bridge b) {
	return a.length < b.length;
}

bool DCompare(dis a, dis b) {
	return a.max < b.max;
}

int ans[MAXN];

int main() {
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld", &isl[i].left, &isl[i].right);
		}
		
		for (int i = 0; i < m; i++) {
			scanf("%lld", &b[i].length);
			b[i].number = i + 1;
			b[i].isUsed = false;
		}
		for (int i = 1; i < n; i++) {
			d[i].min = isl[i].left - isl[i - 1].right;
			d[i].max = isl[i].right - isl[i - 1].left;
			d[i].num = i;
			d[i].isOK = false;
		}
		d[0].max = -1;
		sort(b, b + m, BCompare);
		bool can = true;
		int num = 1;
		for (int i = 0; i < m; i++) {
			sort(d, d + n, DCompare);
			for (int j = 1; j < n; j++) {
				if (b[i].length <= d[j].max&&b[i].length >= d[j].min && !d[j].isOK) {
					ans[d[j].num] = b[i].number;
					d[j].isOK = true;
					num++;
					break;
				}
			}
		}
		if (num >= n) {
			can = true;
		}
		else {
			can = false;
		}
		if (can) {
			printf("YES\n");
			for (int i = 1; i < n; i++) {
				if (i == n - 1) {
					printf("%d\n", ans[i]);
				}
				else {
					printf("%d ", ans[i]);
				}
			}
		}
		else {
			printf("NO\n");
		}
	}
}

能通过所有题目给的用例，但是能不能AC就不太清楚了，没有注册账号

此题链接：http://codeforces.com/problemset/problem/555/B

发表于 2020-04-08 16:16:57 回复(0)

errorAndDebug

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
using namespace std;

const int MAX=1000001;

queue<int> bridgeQueue;

void init(){
while (!bridgeQueue.empty())
bridgeQueue.pop();
}

struct Island{
long long l;
long long r;
}island[MAX];

struct Bridge{
long long len;
int index;
bool used;
}bridge[MAX];

bool cmp(Bridge a,Bridge b){
return a.len<b.len;
}

int main(){
int bridgeNum,islandNum;
init();
while(scanf("%d%d",&islandNum,&bridgeNum)!=EOF){
for(int i=0;i<islandNum;i++){
scanf("%lld%lld",&island[i].l,&island[i].r);
}

for(int i=1;i<=bridgeNum;i++){
scanf("%lld",&bridge[i].len);
bridge[i].index=i;
bridge[i].used=false;

}

sort(bridge+1,bridge+bridgeNum+1,cmp);

int dis;
bool finish;//阶段完成

for(int i=1;i<islandNum;i++){
dis=island[i].l-island[i-1].r;
for(int j=1;j<=bridgeNum;j++){
finish=false;
if(bridge[j].len>=dis&&!bridge[j].used){
bridgeQueue.push(bridge[j].index);
bridge[j].used=true;
finish=true;
break;
}
}
if(!finish) break;
}

if(finish){
printf("YES\n");
printf("%d",bridgeQueue.front());
bridgeQueue.pop();
while(!bridgeQueue.empty()){
printf(" %d",bridgeQueue.front());
bridgeQueue.pop();
}
}else{
printf("NO\n");
}

}
}

发表于 2020-03-18 16:33:48 回复(1)

提交观点

问题信息

难度：

2条回答 0收藏 1219浏览

CodeForces 555B Case of Fugiti

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题