Atcoder Grand Contest 023

023D Go Home

题目描述

点此看题

解法

直接判断当前状态的决策是困难的，我们不妨逆推整个过程。考虑最后电车一定是再 \(1/n\) 停止的，那么我们大胆猜测，如果 \(p_1\geq p_n\)，那么电车会先到 \(1\) 处，如果 \(p_1，那么电车会先到 \(n\) 处。下面给出 \(p_1\geq p_n\) 会先到 \(1\) 处的证明（另一部分可以类似地证明）：

• 若 \(n=2\)，显然成立。
• 若 \(n>2\) 并且 \(s>x_{n-1}\)，则除了 \(n\) 都会投票往左走，结论成立。
• 若 \(n>2\) 并且 \(s\leq x_{n-1}\)，则如果列车到达 \(1\) 之前没有到达过 \(n-1\)，则结论成立；否则可以化归到第二种情况。

那么考虑 \(n\) 处到达的时间一定是 \(1\) 处到达的时间加上 \(x[n]-x[1]\)，并且 \(n\) 就是最后到达的节点。那么等效子问题就特别明显了，我们让 \(p_1\leftarrow p_1+p_n\)，然后把 \(n\) 删去，递归下去即可。递归的边界是不满足 \(x[l]，时间复杂度 \(O(n)\)

#include 
#define int long long
const int M = 100005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,s,x[M],p[M];
int calc(int l,int r,int f)
{
	if(s<=x[l]) return x[r]-s;
	if(s>=x[r]) return s-x[l];
	if(p[l]>=p[r])
	{
		p[l]+=p[r];
		return (f==r)*(x[r]-x[l])+calc(l,r-1,l);
	}
	p[r]+=p[l];
	return (f==l)*(x[r]-x[l])+calc(l+1,r,r);
}
signed main()
{
	n=read();s=read();
	for(int i=1;i<=n;i++)
		x[i]=read(),p[i]=read();
	printf("%lld\n",calc(1,n,p[1]