AtCoder-JOIOPEN2022_A シーソー
开局考虑二分，然后不会做，没想到不需要二分。
以初始的重心为基准，记为 \(mid\)，可以对操作 \(i\) 次得到的所有可能区间求出重心在 \(mid\) 左侧且最靠右的以及在 \(mid\) 右侧且最靠左的两个区间，容易发现这两个区间左右端点都差 \(1\)，记靠左的一个为 \([l_i,r_i]\)，考虑操作 \(i+1\) 次得到的区间 \([l_{i+1},r_{i+1}]\)，发现 \([l_i,r_i-1]\) 与 \([(l_i+1)+1,r_i+1]\) 一定分列 \(mid\) 左右两侧，中间还有一个区间 \([l_i+1,r_i]\)，所以 \([l_{i+1},r_{i+1}]\) 只用判断 \([l_i+1,r_i]\) 的重心位置就能求出。
对操作次数 \(i\) 计算出 \([l_i,r_i]\) 以及 \([l_i+1,r_i+1]\) 重心与 \(mid\) 的距离，按照某一维排序，枚举排序这维的最大值，后面更大的只能取另一维。
现证明这样算出的答案一定能取到，可以归纳，以此时在 \([l_i,r_i]\) 为例，在 \([l_i+1,r_i+1]\) 同理。此时如果可以走到 \([l_{i+1},r_{i+1}]\) 就走，否则走 \([l_{i+1}+1,r_{i+1}+1]\)，发现不能走到 \([l_{i+1},r_{i+1}]\) 说明它就是 \([l_i,r_i-1]\)，那么 \([l_i+1,r_i]\) 重心更靠右，一定能走到且合法。
提交记录：Submission - AtCoder
标签：AtCoder,2024.01,重心,乱写,mid,区间,杂题 From： https://www.cnblogs.com/SoyTony/p/17973322/Problems_in_January_2024_2