负载平衡_牛客博客

问题 : #6013. 「网络流 24 题」负载平衡

时间限制: 1 Sec 内存限制: 256 MB
</center>

题目描述

G 公司有 $n$ 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

输入

文件的第 $1$ 行中有 $1$ 个正整数 $n$ ，表示有 $n$ 个仓库。
第 $2$ 行中有 $n$ 个正整数，表示 $n$ 个仓库的库存量。

输出

输出最少搬运量。

样例输入

5
17 9 14 16 4

样例输出

提示

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
    int n, m, min, s[10100], a[10100];
    long long sum;
    while(~scanf("%d", &n))
    {
        min = 0;
        sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &s[i]);
            sum += s[i];
        }
        m = sum / n;
        a[0] = 0;
        for (int i = 1; i < n; i++)
            a[i] = a[i - 1] + s[i] - m;
        sort(a, a + n);
        for (int i = 0, j = n - 1; i < j; i++, j--)
            min += a[j] - a[i];
        printf("%d\n", min);
    }
    return 0;
}