固安住房和城乡建设网站,福州网站运营,响应式网站的尺寸,广州澄网站建设公司正题
题目链接:https://www.luogu.com.cn/problem/AT3955 题目大意 nnn个房子在一个坐标轴上#xff0c;第iii个有pip_ipi个人在位置xix_ixi#xff0c;开始所有人都在一辆在位置sss的车上#xff0c;每一时刻#xff0c;每个人都会投票决定车的走向#xff0c;票多的…正题
题目链接:https://www.luogu.com.cn/problem/AT3955 题目大意
nnn个房子在一个坐标轴上第iii个有pip_ipi个人在位置xix_ixi开始所有人都在一辆在位置sss的车上每一时刻每个人都会投票决定车的走向票多的赢求最后一个人的回家时间。
注意每个人不一定会投回家的方向有可能他会帮助其他乘客下车后再回家更优。 解题思路
我们考虑111和nnn哪个先回家结论就是如果p1≥pnp_1\geq p_np1≥pn那么111一定先比nnn回家反之同理。 证明的话就是如果往右走的票多那么等这些票下车后一定有一个时间使得左边比右边多不然就是直接走右边。
所以这种情况下nnn一定比111晚那么111早到家就意味着nnn早到家那么nnn的人就会和111的人投票一样所以我们可以相当于删去nnn然后答案加上xn−x1x_n-x_1xn−x1且让p1pnp_1p_np1pn。一直递归下去即可。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,s,x[N],p[N],f[N],ans;
ll solve(ll l,ll r,ll last){if(sx[l])return x[r]-s;if(sx[r])return s-x[l];if(p[l]p[r]){p[r]p[l];return solve(l1,r,r)((lastl)?(x[r]-x[l]):0);}else{p[l]p[r];return solve(l,r-1,l)((lastr)?(x[r]-x[l]):0);}
}
int main()
{scanf(%lld%lld,n,s);for(ll i1;in;i)scanf(%lld%lld,x[i],p[i]);printf(%lld\n,solve(1,n,(p[1]p[n])?n:1));
}
