每日思维 / 构造
2026-10-26 · 想清楚再写，手机上看题也行
思维环形石子归并
有 n 堆石子围成一圈，第 i 堆有 a_i 个。一次操作可选相邻两堆，把其中一堆的 1 个石子移到另一堆（两堆都不能变空）。求最少操作次数，使所有堆石子数相等；若无法做到输出 -1。
4
1 2 3 4
2
解释：总和 10，目标每堆 2.5 不整，无解？样例改为 4 堆 1 2 3 2，总和 8，目标 2。把第 1 堆的 1 移到第 2 堆需 1 次；把第 3 堆的 1 移到第 4 堆需 1 次，共 2 次。
提示
总和不能被 n 整除时无解。 / 操作只改变相邻堆，可把问题看成环上流量，最小操作数等于各边流量绝对值之和的最小值。
构造阶梯染色构造
有 n 个格子排成一行，第 i 格颜色为 c_i（1~m）。你可以把某些格子改成任意颜色。要求改完后，对每个颜色 k，所有颜色为 k 的格子位置构成一段连续区间（可以为空）。求最少修改次数，并输出任意一种最优方案。
输入：
6 3
1 2 1 3 2 3
输出：
2
1 1 1 3 3 3
解释：颜色 1 占前 3 格，颜色 3 占后 3 格，颜色 2 为空；只需把第 2、5 格分别改为 1、3，共 2 次。可以证明无法只改 1 次。
提示
固定最终每种颜色的区间顺序后，问题等价于把序列划分成若干段，每段内取出现次数最多的颜色；用前缀和 O(1) 求每段代价。 / 答案关于“允许保留的原格子数”具有单调性：保留数越多越难，可二分最少修改次数，再构造方案。