n 个整数排成一个环,每次可以选择一个 x 并把环上相邻的某两个整数其中一个加上 x,另一个减去 x。求把所有整数都变成 0 的最小操作次数。
1≤n≤105,0≤∣ai∣≤109。
考虑设序列 si=a1+a2+a3,…,+ai,那么一次操作相当于:
-
选定一个 1∼n−1 的整数 i,让 si 减去任意一个整数 x(可正可负);
-
让 s1∼n−1 减去任意一个整数 x(可正可负);
目标是让所有 si 都变成 0。
那么若 sn=0 就一定无解,否则注意到第一种操作相当于任意更改 s1∼n−1 中的某个数,那么可以把 s1∼n−1 都变成同一个数 y,最后若 x=0 再进行一次第二种操作。
那么解法就呼之欲出了,只要排序找到 s1∼n 中出现次数最多的数并统计出它的出现次数 cnt,答案即为 n−cnt。时间复杂度 O(nlogn)。
注意开 long long
。