CF675C Money Transfers 做题记录

$n$ 个整数排成一个环，每次可以选择一个 $x$ 并把环上相邻的某两个整数其中一个加上 $x$，另一个减去 $x$。求把所有整数都变成 $0$ 的最小操作次数。

$1\le n\le 10^5$，$0\le |a_i|\le 10^9$。

考虑设序列 $s_i=a_1+a_2+a_3,\dots,+a_i$，那么一次操作相当于：

1. 选定一个 $1\sim n-1$ 的整数 $i$，让 $s_i$ 减去任意一个整数 $x$（可正可负）；

2. 让 $s_{1\sim n-1}$ 减去任意一个整数 $x$（可正可负）；

目标是让所有 $s_i$ 都变成 $0$。

那么若 $s_n\not=0$ 就一定无解，否则注意到第一种操作相当于任意更改 $s_{1\sim n-1}$ 中的某个数，那么可以把 $s_{1\sim n-1}$ 都变成同一个数 $y$，最后若 $x\not=0$ 再进行一次第二种操作。

那么解法就呼之欲出了，只要排序找到 $s_{1\sim n}$ 中出现次数最多的数并统计出它的出现次数 $cnt$，答案即为 $n-cnt$。时间复杂度 $O(n\log n)$。

注意开 long long。