题解：AT_abc429_d [ABC429D] On AtCoder Conference

· · 题解

题目大意

有一环，长为 M，有 N 个人，第 i 个人位于 A_i。给了个 C(C\le N)。这个环的坐标范围为 0\sim M-1。

定义 X_i 为：从 (i+0.5) 开始移动，遇到的人数达到或超过 C 时遇到的人数。如果在结束的位置有多个人，那么这些人亦计入 X_i。

求 \sum_{i=0}^{M-1} X_i。

思路

注意到，任意的一对在 $[A_i,A_{i+1}]$ 范围内的整数 $i,j$，都满足 $X_i=X_j$。用这个性质来做。答案乘上区间之间的长度。 但它是个环。 因此需要做环上的特殊处理，比如 $[A_n,M-1]\cap[0,A_1-1]$ 这段区间需要格外处理。 再考虑怎么求，设现在位于 $x$，进行分类讨论： 1. 如果 $[x,M-1]$ 区间的人数小于 $C$，还要加上另一端的。 2. 否则直接做。 那么求终止位置只需要二分即可。 [提交记录。](https://atcoder.jp/contests/abc429/submissions/70453371)