Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine)) 题解

2023-11-06 19:05:16

A

枚举

利用调和级数+前缀和优化。

每次将最大的两个丢到最后即可。

利用平衡树得到最后的序列，相邻两位之间是\(<\)或\(\leq\) 。用组合数求解。

考虑二分答案。

可以从原点开始\(bfs\)。一个很重要的观察是，如果\(x\)能到\(y\)，且\(t\)能到\(y\)则\(x\)能到\(t\)或者\(t\)能到\(x\)。

这样遍历的点是互相不同的。

枚举一个数\(x\)。将\(\geq x\)的看作\(1\)，其余的看作\(0\) 。

求最少的操作次数使得序列变成\(000...0011..111\)。

考虑一段区间\(1111\)的移动。令\(t_i\)表示\(i\)的出发时间。为了避免两段\(1\)相撞的情况，可以理解成等到不可能撞到前面一段时才开始。

可以将\(1\)看作\(1\)，\(0\)看作\(-1\)，求一边最大前缀和即可,即最左边出发的时间。