引理
若M个小朋友排成一行,手中分别有A[1]~A[n]个糖果,在每一步操作中,可以让某个人把自己手中的一个糖果交给他旁边的一个人,求至少需要多少步操作才能让每个小朋友手中的糖果数相等?
分析:
-
在第一个人中,一定会向第二个人拿糖果或者向第二个人给糖果,其数量为
|A[1] - avg|
,更新A[2]
-
在第二个人中,一定会向第三个人拿糖果或者向第三个人给糖果,其数量为
|A[2] - avg|
,更新A[3]
-
…
-
在第
(n - 1)
个人中,一定会向第n
个人拿糖果或者向第n
个人给糖果,其数量为|A[n - 1] - avg|
,更新A[n]
即使在某个时刻有某个A[i]
被减为负数也没关系,因为接下来A[i]
会从A[i + 1]
处拿
步骤
-
1、求出每个糖果数-糖果平均数
avg
的值作为数组C[]
,则C[i] = A[i] - avg
,其中i∈ [1,n]
-
2、求出数组
C[]
的前缀和S[]
,则达到目标所需要的最小步数是$$ Min = \sum_{i=1}^n\| G[i] | $$
算法1
.....此处是一个环形的糖果交换问题,则一定存在一种最优解使得某两个人之间没有纸牌交换。就是要么a给b,要么b给a,不能a给了b,b又给了a,如果存在这样的交换,就不是最优解了,可以用反证法证明。
不妨设S[i]
是本来的数组减去平均值之后的前缀和,假设我们从第k个位置断开(严格的来说是第k个位置的下一条边断开),那么序列就变成了:
-
A[k + 1] = S[k + 1] - S[k]
-
A[k + 2] = S[k + 2] - S[k]
…
A[n] = s[n] - s[k]
A[1] = S[1] + S[n] - S[k] -
…
-
A[k] = S[k] + S[n] - S[k]
-
断开之后则可以看成是排成一行,引用上面的引理
则相当于求|S[k + 1] - S[k]| + |S[k + 2] - S[k]| + … + |S[n] - S[k]| + |S[n] - S[k] + S[1]| + |S[n] - S[k] + S[2]| +…+|S[n] - S[k] + S[k]|的最小值,由于S[n] = 0
则相当于求|S[1] - S[k]| + |S[2] - S[k]| +…+ |S[k] - S[k]| + |S[k + 1] - S[k]| +…+ |S[n] - S[k]| 的最小值,其中k∈ [1,n]
则此问题变成了货仓选址问题,找到中位数,累加出每个点到中位数的距离之和,链接如下
https://www.acwing.com/file_system/file/content/whole/index/content/132044/
步骤
-
1、计算出本来数组减去平均值之后的前缀和s[]
-
2、对数组s[]进行排序
-
3、累加出每个点到中位数的距离之和
res += Math.abs(s[i] - s[(n + 1)/2])
时间复杂度 $O(nlogn)$
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] s = new int[1000010];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long sum = 0;
for(int i = 1;i <= n;i++)
{
s[i] = scan.nextInt();
sum += s[i];
}
//求平均值
int avg = (int) (sum/n);
//求减去平均值之后的数组的前缀和
for(int i = 1;i <= n;i++)
{
s[i] = s[i] - avg + s[i - 1];
}
Arrays.sort(s, 1, n + 1);
long res = 0;
for(int i = 1;i <= n;i++) res += Math.abs(s[i] - s[(n + 1)/2]);
System.out.println(res);
}
}
算法2
步骤
-
1、计算出本来数组减去平均值之后的前缀和s[]
-
2、通过找第k小的方式找出中位数,其中这里的时间复杂度是
O(n)
-
3、累加出每个点到中位数的距离之和
res += Math.abs(s[i] - s[k])
注意:找第k小的数,我们只需要进入左右两半二者之一继续递归,在平均情况下,复杂度为n + n/2 + n/4 +... + 1 = O(n)
时间复杂度 $O(n)$
Java 代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//找第k个位置 时间复杂度O(n)
public static int quick_sort(int[] q,int L,int R,int k)
{
if(L >= R) return L;
int i = L - 1;
int j = R + 1;
int x = q[(L + R) >> 1];
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j)
{
int t = q[i];
q[i] = q[j];
q[j] = t;
}
}
//j是左边界
if(k <= j) return quick_sort(q,L,j,k);
else return quick_sort(q,j + 1,R,k);
}
static int[] s = new int[1000010];
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long sum = 0;
for(int i = 1;i <= n;i++)
{
s[i] = scan.nextInt();
sum += s[i];
}
//求平均值
int avg = (int) (sum/n);
//求减去平均值之后的数组的前缀和
for(int i = 1;i <= n;i++)
{
s[i] = s[i] - avg + s[i - 1];
}
int k = quick_sort(s,1,n,(n + 1) >> 1);
long res = 0;
for(int i = 1;i <= n;i++) res += Math.abs(s[i] - s[k]);
System.out.println(res);
}
}
大佬麻烦问下为啥可以断开啊,我能理解不能互相交换但是还是不太懂
思路清晰!good
谢谢hh
优秀!打call!
谢谢hh