CF675C Money Transfers 做题记录

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

1n1051\le n\le 10^50ai1090\le |a_i|\le 10^9

考虑设序列 si=a1+a2+a3,,+ais_i=a_1+a_2+a_3,\dots,+a_i,那么一次操作相当于:

  1. 选定一个 1n11\sim n-1 的整数 ii,让 sis_i 减去任意一个整数 xx(可正可负);

  2. s1n1s_{1\sim n-1} 减去任意一个整数 xx(可正可负);

目标是让所有 sis_i 都变成 00

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

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

注意开 long long