Description:


给你一个排列\(p_1,p_2,\dots,p_n\),第\(i\)个元素的权重为\(a_i\)。

你首先要把排列切成两个非空子集,前缀和后缀。

然后移动其中的元素,你可以将前缀中的元素移到后缀中,也可以反过来,移动\(p_i\)需要付出\(a_i\)的代价。

问最少付出多少代价,可以使得前缀中的元素均小于后缀中的元素,或其中一个为空。

\(n\leq 200\ 000, a_i \leq 10^9\)

继续阅读

Description:


无限长的一维坐标轴上有\(n\)个球,每个球的坐标为\(x_i\),速度为\(v_i\),并以\(p_i\)的概率向右运动,\(1-p_i\)的概率向左运动,求第一次碰撞产生时的期望时间。永远不产生碰撞的贡献为0。

\(1\leq n \leq 10^5\)

继续阅读