貪心2題

微軟面試題

有n個小朋友坐成一圈，每人有a[i]個糖果。

每人隻能給左右兩人傳遞糖果。

每人每次傳遞一個糖果代價為1。

求使所有人獲得均等糖果的最小代價。

輸入格式

第一行輸入一個正整數n，表示小朋友的個數。

接下來n行，每行一個整數a[i]，表示第i個小朋友初始得到的糖果的顆數。

輸出格式

輸出一個整數，表示最小代價。

資料範圍

1≤n≤10000001≤n≤1000000

資料保證一定有解。

輸入樣例：

4
1
2
5
4
           

輸出樣例：

4
           

說明：

其中x為傳遞糖果所需要用的代價數，

若x>0，則說明傳遞的方向是從ai->a[i-1];

若x<0,那麼傳遞的方向是從a[i-1]>ai;

分析題目：目标+限制

目标：要使得代價和最小。

也就是使得|x1|+|x2|+…|xn|最小

限制：使得a[i]=ave(a);//ave(a)也就是平均值

這是一個多元代數式，求最小值，應該想辦法轉化為1元代數式。

我們嘗試找出關系式：

對于每個a[i]:

_a表示a的平均值

a[1]-_a=x2-x1

a[2]-_a=x3-x2

…

a[n-2]-_a=x[n-1]-x[n-2]

a[n-1]-_a=x[n]-x[n-1]

a[n]-_a=x[1]-x[n]

整理為a一邊，x一邊：

x[n]=x[1]+_a-a[n];

x[n-1]=x[n]+_a-a[n-1]

帶入x[n]：其實尾部兩式直接相加即可得到x[n-1]

x[n-1]-x1=2_a-a[n]-a[n-1];

x[n-2]=x[n-1]-x[n-2]+_a;

尾部三式相加整理：

x(n-2)-x1=3_a-a[n]-a[n-1]-a[n-2];

又上面式子：

x[n]=x[1]+（_a-a[n]）;

x[n-1]=x[1]+（2_a-a[n]-a[n-1]）;

x(n-2)=x[1]+（3_a-a[n]-a[n-1]-a[n-2]）;

…

xi=x[1]+【(n+1-i)_a-a[n]-a[n-1]-a[n-2]-…a[i]】;

特别的：

當i=1時候：

由于n_a=(a[1]+a[2]+…a[n])

是以：x[1]=x[1]+0;

可以總結每一項都可以由x1表示

而且可以轉化為xi=x1+ci的形式：

又c[n]=_a - a[n]

c[n-1]=2_a - a[n]-a[n-1]

c[n-2]=3_a - a[n]- a[n-1] -a[n-2]

是以：會發現每一項都比前一項多了一個_a再多減去一個a[n]

c[i]=c[i+1]+_a-a[i];

注意c[1]=0;(x1=x1+0)

進而将|x1|+|x2|+|x3|+…|xn|的最小化問題轉化為|x1+c1|+|x1+c2|+…|x1+cn|的坐标模型：

也就是坐标軸上的點

c1,c2,c3…cn到x1的最小值：

而由幾何意義不難想到:

x1在中位數的時候取得最小值：

即x1=c[i+1/2];(i從1開始，如果i從0開始，x1=c[n/2])；

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000010;
typedef long long LL;
int n;
int a[N];
LL c[N];
int main()
{

scanf("%d",&n);
LL sum=0;
for(int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
    sum+=a[i];
}
LL ave=sum/n;
for(int i=n;i>1;i--){
    c[i]=c[i+1]+ave-a[i];
}
c[1]=0;
sort(c+1,c+n+1);
LL res=0;

for(int i=1;i<=n;i++){
    res+=abs(c[i]-c[(n+1)/2]);
}
printf("%lld\n",res);
    return 0;
}