站外题求助

学术版

ARIS2_0 @ 2024-11-28 15:40:17

给定一个长度为 n 的正整数数列 a 满足 (\sum_{i=1}^n a_i)\mod n=0。

现定义一次操作为：

选择一个 i(1\le i\le n) 与一个 k(1\le k\le a_i)，将 a_i 减去 k，同时使 a_i 的上一个数或下一个数加上 k。特别地，a_1 的上一个数是 a_n，a_n 的下一个数是 a_1。

求当满足 a_1=a_2=\dots=a_n 时，需要的最小操作数。

洛谷有没有类似的题目，若没有能否讲一下大致做法

by not_clever_syl @ 2024-11-28 15:47:12

https://www.luogu.com.cn/problem/P2125

by ARIS2_0 @ 2024-11-28 15:49:19

@not_clever_syl thx。

@Hagasei n\le 10^5,a_i\le 110。

by Hagasei @ 2024-11-28 15:49:40

@not_clever_syl 这不一样吧，最少操作次数和最小总变化量。

by ARIS2_0 @ 2024-11-28 15:49:43

感觉是基于值域的做法。

by not_clever_syl @ 2024-11-28 15:52:16

@Hagasei 最小化这两个应该有点联系吧，而且你问的是类似题目

by Polarisx @ 2024-11-28 16:36:35

两个题可以转换吧，最后变成求 \min \sum_{i=0}^{n-1} [c_i\not= x]，求个众数就行了吧？

by ARIS2_0 @ 2024-11-29 13:42:46

@Polarisx 好，thx。