求问一道算法题

有1到n n个数字，最开始它们分布在三个group A,B,C中，给定n和初始A B C 里的数字，解决：
每一步，可以从一个group中选一个数字移动到其他任何一个group中（可以把某个group移空）
要求是最终的三个group，group A 里的最大值小于groupB里的最小值，group B里的最大值小于group C里的最小值
求最少步数
n的范围是10^5

三个group 最终肯定是排好序的。
换句话第一个group 如果是 1 2 3 。。。 x, 第二个就是 x + 1, x + 2 ... x + y, 第三个 x + y + 1 ... n

提前算好每个group的数组p, p[i] 代表把 1 到i 这些数放到这个group 需要多少步。

然后枚举第一个group i， 如果我把 1 到i 放进第一个group，那么i + 1 到n 一定要放到2 3 group。放到2 3 的最少步数可以后缀提前处理。

复杂度O(n)

这道题挖掘一下前缀和的数学公式就行了。。
=======================
首先把0到N-1一共N个数当作index，把group label按照这个index排列起来。。
排好以后可能得到类似“AAABBCCAACCBB”的字符串X。。。
最终需要的字符串肯定是“AAAAABBBBBCCCC”这种的模式
=================================
为了计算最小的步数，需要预先计算三组长度为"N+1"的前缀和"SA/SB/SC"
SA[i]代表X[:i]中group 不为A的个数，SB/SC以此类推
==================================
假设我们目标串里面B与C的开头index分别是 i 与 j
利用前缀和得到需要的操作数量，就是(SA[i]-SA[0])+(SB[j]-SB[i])+(SC[N]-SC[j])。。
里面SA[0] = 0, SC[N]为常数，把上面式子按照 i 与 j 变形，
可以得到(SC[N]-SA[0])+(SA[i]-SB[i])+(SB[j]-SC[j])

这里就非常的清楚了，从后往前预先计算（SB[j]-SC[j]）的最大值
然后从前往后枚举 i 计算 (SA[i]-SB[i])，加上对应位置预先计算出来的（SB[j]-SC[j]）最大值，就是答案。。。
===========
顺便球一波加米。。。。

补充内容 (2025-04-23 13:34 +08:00):

复习一下前缀和的公式，
对于长度为m的nums得到长度为m+1的前缀和psum
利用前缀和求子数组和，sum(nums[i:j]) = psum[j] - psum[i]

bbbbbk 发表于 2025-4-19 22:41
请问 “放到2 3 的最少步数可以后缀提前处理” 如何做到O(N), 只想到了N^2的做吗

假设suff[i] 是指吧i 到n放到group 2, 3， suff[i] = min(suff[i + 1] + place i on 2, suff3[i + 1] + min(place i on 2, place i on 3))
suff3[i] 代表 把i 到n 都放到group 3。
suff[i] 代表 把i 到n 都放到group 2 3 并且group2 不为空。

n和数字各不相同

bbbbbk 发表于 2025-04-19 15:07:46
n和数字各不相同

n个数字各不相同

提示：前缀和

_图图 发表于 2025-04-19 17:05:36
提示：前缀和

没get到… 大佬能说说解法吗

预处理三个前缀和 用于 range sum。
每个前缀和表示将 1-x 都放在该 group 的操作数
枚举两个 pointer 把一到 x 分为三段，每段可以为空
三个 group 从 A 到 C 用三段互不相交的range sum。
但这样是 n^2 的复杂度
用楼上的提前出来可以到达 n

66j 发表于 2025-4-20 01:06
三个group 最终肯定是排好序的。
换句话第一个group 如果是 1 2 3 。。。 x, 第二个就是 x + 1, x + 2 ... ...

请问 “放到2 3 的最少步数可以后缀提前处理” 如何做到O(N), 只想到了N^2的做吗

66j 发表于 2025-04-19 20:12:06
假设suff 是指吧i 到n放到group 2, 3， suff = min(suff + place i on 2, suff3 + min(place i

明白了 谢谢太6了！