AtCoder Grand Contest 013 C：Ants on a Circle

题目传送门：https://agc013.contest.atcoder.jp/tasks/agc013_c

题目翻译

给你一个周长为\(L\)的圆，有\(N\)只蚂蚁在圆上爬，速度为一单位距离每秒。有的蚂蚁是逆时针的，有的蚂蚁是顺时针的，蚂蚁互相碰面会转向，问你\(T\)秒后每只蚂蚁分别在什么地方。\(L，T\leqslant 10^9,N\leqslant 10^5\)

题解

碰面转向相当于不转向交换编号，所以我们可以求出最后每只蚂蚁会在哪个地方。然后只需要关注第一只蚂蚁最后的\(pos\)的排名就行了。容易发现，当有一只蚂蚁从\(N-1\)爬到\(0\)时，\(1\)号蚂蚁的\(rk++\)，反着就\(rk--\)。

时间复杂度：\(O(N)\)

空间复杂度：\(O(NlogN)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

int n,rk,L,T;

int pos[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

int main() {

	n=read(),L=read(),T=read();

	for(int i=1;i<=n;i++) {

		int x=read(),w=read();

		if(w==2)pos[i]=x-T;

		else pos[i]=x+T;

		rk+=pos[i]/L;

		if(pos[i]%L<0)rk--;

		pos[i]=(pos[i]%L+L)%L;

	}

	sort(pos+1,pos+n+1);

	rk=(rk%n+n)%n;

	for(int i=rk+1;i<=n;i++)

		printf("%d\n",pos[i]);

	for(int i=1;i<=rk;i++)

		printf("%d\n",pos[i]);

	return 0;

}

巴特西

AtCoder Grand Contest 013 C：Ants on a Circle

题目翻译

题解

最新文章

热门文章