AtCoder Grand Contest 023 D - Go Home

题意

现在有一个数轴，有n个公寓。然后第i个公寓在xi位置上，且当前第i个公寓住pi个人。那么现在我们从s开始出发。然后就会*投票（多数人暴政），会选择当前车子往左往右走一格，若票数相同就走左。当然每个人都是自私的且非常聪明的（这并不意味这他会一定往自己家走）。问最早什么时候送完所有人。

前言

其实这题是我无聊找atcoder题时找到的。
当时想了想感觉没思路，后来才发现奇妙无比。

题解

首先我们分析一下这些自私的人会怎么选。

假设当前只剩下最左边和最右边的两家公寓。
如果最左边的公寓人数大于最右边的人数，那么最右边的人数最聪明的做法是把全票投给最左边的人。
为什么呢？
假设有这么个数据：
4 10
1 10
12 5
13 5
14 5
你可能会想说最右边的三个公寓齐心协力来对抗左边的一个公寓。
然鹅当车子往右边走的时候，人数会逐渐减少，反而让最左边的公寓占了上风。
然后就往右边走了一段不必要的路程。
感觉这个谦让的思维很像“海盗分金问题”。

然后我们就一直把右边的人投票投进去左边的人，直到出现一个右边的人大于左边的人。
然后这样周而复始。
当起点左边或右边没有人反抗了之后，就可以停止了。

好一道思维神题。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1000010;

int n;
long long st,ans,x[maxn],y[maxn];

int main()
{
	scanf("%d%lld",&n,&st);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
	}
	int l=1;
	int r=n;
	while (l<=r)
	{
		if (x[l]>=st) 
		{
			ans=ans+x[r]-st;
			break;
		}
		if (x[r]<=st)
		{
			ans=ans+st-x[l];
			break;
		}
		ans=ans+x[r]-x[l];
		if (y[l]>=y[r])
		{
			while (y[l]>=y[r] && l<r)
			{
				y[l]=y[l]+y[r];
				r--;
			}
		}
		else
		{
			while (y[l]<y[r] && l<r)
			{
				y[r]=y[r]+y[l];
				l++;
			}
		}
	}
	printf("%lld\n",ans);
}