「AGC023D」 Go Home

神题。

首先我们可以倒着考虑。

当车到达最后一栋楼的时候，车上一定只有到这栋楼的员工。

当车到达倒数第二栋楼的时候，车上一定只有到达剩下两栋楼的员工。

设这两栋楼分别为 \(a,b\)，且 \(x_a<x_b\)。如果当前公交车不在 \(a,b\) 之间，那么直接往一个方向移动肯定是最优秀的。否则，若 \(p_a>p_b\)，则一定会先往 \(a\) 的方向移动。

当车到达倒数第三栋楼的时候，车上一定只有到达剩下三栋楼的员工。

设这三栋楼分别为 \(a,b,c\)，且 \(x_a<x_b<x_c\)。如果当前公交车不在 \(a,c\) 之间，那么直接往一个方向移动肯定是最优秀的。

否则会有一类很特殊的情况：有汽车在 \(a,b\) 之间，且 \(p_a>p_c,p_a<p_b+p_c\)。这个时候如果 \(c\) 把票投给向自己家的方向，反而会使自己到家的时间变晚——汽车会先向 \(c\) 方向走，再到达 \(a\) 楼，最后到达 \(c\) 楼。

所以 \(c\) 一定会把票投给向 \(a\) 方向走。

我们发现这等价于把 \(c\) 楼的人全部看作 \(a\) 楼的人，然后再加上公交车到 \(a\) 楼的路程，使公交车移动到 \(a\) 楼。

然后你会发现我们上面分析的过程可以通过递归来实现，然后这个题就做完了。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

/*---Never Enough---*/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

ll x[maxn],p[maxn];

ll n,s;

ll calc(ll l,ll r,ll t){

	if(s<x[l]) return x[r]-s;

	if(x[r]<s) return s-x[l];

	if(p[l]>=p[r]){

		p[l]+=p[r];

		return calc(l,r-1,l)+(t==r?x[r]-x[l]:0);

	}

	else{

		p[r]+=p[l];

		return calc(l+1,r,r)+(t==l?x[r]-x[l]:0);

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>n>>s;

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

		cin>>x[i]>>p[i];

	}

	cout<<calc(1,n,p[1]>=p[n]?n:1)<<'\n';

	return 0;

}

巴特西

「AGC023D」 Go Home

「AGC023D」 Go Home

最新文章

热门文章