正題

題目鏈接:https://www.luogu.com.cn/problem/AT3955

---

題目大意

$n$個房子在一個坐標軸上，第$i$個有$p_i$個人在位置$x_i$，開始所有人都在一輛在位置$s$的車上，每一時刻，每個人都會投票決定車的走向，票多的贏，求最后一個人的回家時間。

注意每個人不一定會投回家的方向，有可能他會幫助其他乘客下車后再回家更優。

---

解題思路

我們考慮$1$和$n$哪個先回家，結論就是如果$p_1\ge p_n$那么$1$一定先比$n$回家，反之同理。
證明的話就是如果往右走的票多那么等這些票下車后一定有一個時間使得左邊比右邊多，不然就是直接走右邊。

所以這種情況下$n$一定比$1$晚，那么$1$早到家就意味著$n$早到家，那么$n$的人就會和$1$的人投票一樣，所以我們可以相當于刪去$n$，然后答案加上$x_n?x_1$且讓$p_1+=p_n$。一直遞歸下去即可。

時間復雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,s,x[N],p[N],f[N],ans; ll solve(ll l,ll r,ll last){if(s<x[l])return x[r]-s;if(s>x[r])return s-x[l];if(p[l]<p[r]){p[r]+=p[l];return solve(l+1,r,r)+((last==l)?(x[r]-x[l]):0);}else{p[l]+=p[r];return solve(l,r-1,l)+((last==r)?(x[r]-x[l]):0);} } int main() {scanf("%lld%lld",&n,&s);for(ll i=1;i<=n;i++)scanf("%lld%lld",&x[i],&p[i]);printf("%lld\n",solve(1,n,(p[1]>=p[n])?n:1)); }

總結

以上是生活随笔為你收集整理的AT3955-[AGC023D]Go Home【结论,递归】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。