【Codeforces 652F】Ants on a Circle

Zarxdy34 posted @ 2016年4月19日 15:52 in Codeforces with tags 构造 , 295 阅读

        最终所有蚂蚁的位置(不管是哪只蚂蚁在哪个位置)是很容易确定下来的,可以看作有所的蚂蚁不管碰撞,一路走到底。

        最终所有蚂蚁的相对位置也是可以确定下来的,因为每次碰撞并不会影响蚂蚁们的相对位置。

        这个问题的难点在于如何判断最后任意一只蚂蚁的位置。

        官方题解里给出了一个比较显然的做法:由于当所有蚂蚁走m次后蚂蚁们的位置集合与初始相同,可以模拟出一只蚂蚁在m的时间里走到了哪个位置,然后其他蚂蚁的位置也就可以确定下来。这样再循环走若干次,最后再走t%m的时间,就能得到所有蚂蚁的最终位置了。

        由于我们只需要知道一只蚂蚁在m的时间里走到了哪里,所以其他蚂蚁的编号我们都先不管。在m的时间里一只蚂蚁最多发生2n次碰撞,所以这个可以开两个堆维护向左、向右走的蚂蚁,每次更新碰撞事件,时间复杂度\(O(nlogn)\)。

        有些时候会发现有两只蚂蚁在我们求出的那个位置上。那么这时再模拟出另一只蚂蚁的最终位置就好了。

        这么写起来稍微会麻烦一点,在评论区里有一个人给出了一个非常简单的做法:

        官方题解里的做法以一只蚂蚁的位置为基础,求出其他蚂蚁的位置。

                  一个更简单的做法是,我们可以通过找最终位置>=0的第一只蚂蚁是哪一只,同样可以求出最终每个位置上的蚂蚁是哪只。

                  假设在某一时刻,位置>=0的蚂蚁是第i只蚂蚁(这里的蚂蚁编号按照排序后的顺序给)。

                  考虑x=0这个点。如果在该时刻之后,有一只蚂蚁从x=m-1走到了x=0,说明有一只蚂蚁排在了第i只蚂蚁的左边,此时位置>=0的蚂蚁是第i-1只蚂蚁;

                  如果在该时刻之后,有一只蚂蚁从x=0走到了x=m-1,说明有一只蚂蚁跑到最右边去了,此时位置>=0的的蚂蚁是第i+1只蚂蚁。

                  非常好的一点是,我们无须关心是哪只蚂蚁从x=0走开了,只需要知道有蚂蚁这么走。

                  于是就可以很轻易地知道最终位置上的位置>=0的第一只蚂蚁是哪只了。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=300010;

int p[maxn],dir[maxn],rank[maxn];
int ans[maxn];
int n,m;
long long t;

bool cmp(const int &a,const int &b) {return p[a]<p[b];}

int main()
{
	scanf("%d%d%I64d",&n,&m,&t);
	t%=(long long)n*m;
	for (int i=1;i<=n;i++)
	{
		char ch[4];
		scanf("%d %s",&p[i],ch);
		p[i]--;
		dir[i]=(ch[0]=='L')?-1:1;
		rank[i]=i;
	}
	sort(rank+1,rank+1+n,cmp);
	int s=0;
	for (int i=1;i<=n;i++)
	{
		if (dir[i]==1) s=(s-(p[i]+t)/m)%n;
		else s=(s-(p[i]-t-m+1)/m)%n;
		p[i]=((p[i]+dir[i]*t)%m+m)%m;
	}
	s=(s+n)%n;
	sort(p+1,p+1+n);
	rotate(rank+1,rank+1+s,rank+1+n);
	for (int i=1;i<=n;i++) ans[rank[i]]=p[i]+1;
	for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1