P6607 [Code+#7] 蚂蚁 题解

P6607 (Code+#7) 蚂蚁 题解

题目:

[Code+#7]蚂蚁

题目描述

在东西排布的两棵树之间悬挂着一条长为 $L$ 的细绳，有 $N$ 只蚂蚁在这条绳上。这些蚂蚁希望通过绳子爬到任何一棵树上，但这条绳太细了，导致两只蚂蚁不能并排爬行，也不能交错而过。

它们想到了一个方法：每只蚂蚁都以每单位时间移动一个单位距离的速度不断向前爬，当迎面碰到另一只蚂蚁时，两只蚂蚁都将立即掉头并继续向前爬。现在，蚂蚁们想知道自己是否能爬下绳子，如果能，它们还希望知道自己爬下绳子所花的时间。为了方便，我们按初始时位置从东到西的顺序对蚂蚁从 $1$ 开始编号。

输入格式

输入的第一行包含两个正整数 $N,L$，保证 $N\le 10^5,L\le 10^9$，且 $N<L$。

输入的第二行包含 $N$ 个正整数，第 $i$ 个数 $p_i$ 表示第 $i$ 只蚂蚁到东侧树木的距离，保证 $p_i$ 随 $i$ 增大严格递增，且 $0<p_i<L$。

输入的第三行包含 $N$ 个整数，第 $i$ 个数 $d_i$ 若为 $1$ 则表示第 $i$ 只蚂蚁一开始朝向西侧，为 $0$ 则表示朝向东侧。

输出格式

输出仅一行，包含 $N$ 个数，第 $i$ 个数表示第 $i$ 只蚂蚁爬下绳子所花时间，四舍五入保留到整数。若第 $i$ 只蚂蚁无法爬下绳子，则输出的第 $i$ 个数为 $-1$。

样例 #1

样例输入 #1

3 6
1 3 5
1 1 0
1
2
3

样例输出 #1

5 5 3
1

提示

样例解释

第三只蚂蚁在爬行 $1$ 个单位时间后遇见第二只蚂蚁并掉头，再爬行 $2$ 个单位时间到西侧树木；

第二只蚂蚁在爬行 $1$ 个单位时间后遇见第三只蚂蚁并掉头，再爬行 $1$ 个单位时间后遇见第一只蚂蚁并掉头，再爬行 $3$ 个单位时间到西侧树木；

第一只蚂蚁在爬行 $2$ 个单位时间后遇见第二只蚂蚁并掉头，再爬行 $3$ 个单位时间到东侧树木。

子任务

子任务 $1$（$17$ 分）

• $1\le N\le 10,L\le 10^5$。

子任务 $2$（$19$ 分）

• $1\le N\le 100,L\le 10^9$。

子任务 $3$（$27$ 分）

• $1\le N\le 5000,L\le 10^9$。

子任务 $4$（$37$ 分）

• $1\le N\le 10^5,L\le 10^9$。

Code:

#include
using namespace std; 
int n,l;
int a[1000001],b[1000001];
int main()
{
	cin>>n>>l;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	for(int i=1;i<=n;i++)
		if(b[i]==0)
			cout<<a[i]<<' ';
	for(int i=1;i<=n;i++)
		if(b[i]==1)
			cout<<l-a[i]<<' ';
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19