洛谷 P4016 负载平衡问题

题目链接：洛谷 P4016 负载平衡问题

算法标签: 贪心、数学

题目

题目背景

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

题目描述

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

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

输入格式

共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含A,C,G,T四个字母。$1≤序列的长度\le 100$。

输出格式

输出最少搬运量。

输入输出样例

输入 #1

5
17 9 14 16 4

输出 #1

题解：

这道题大致的思路是贪心+数学（虽然某谷标签是网络流24题），最主要在于推出结论，之后就可以知道如何求搬运量，而最小搬运量只需要看做某个点只向他左边的点搬运，它只接受右边的点搬运来的货物。

$\overline{a[]}$ 表示平均数，在题解中$\overline {a[ ]} = ave = \frac{a_1+a_2+a_3+…+a_n}{n}$
$x[]_{0.5}$ 表示中位数，在题解中$x[]_{0.5} = med = x[n / 2 + 1]$

我们可以设$g_1, g_2,g_3,…,g_n$ 为第1， 2， 3，…，n个人给他左边人的货物（$g_1$为第1个人给第n个人的货物），设$a_1,a_2,…,a_n$ 为每个人现有的货物。所以可知：

$a_1 - g_1 + g_2 = ave$ -> $g_2 = ave + g_1 - a_1$

所以：

\[ \left\{ \begin{aligned} g_2 &= ave + g_1 - a_1 \\ g_3 &= ave + g_2 - a_2\\ … \\ g_n&=ave + g_{n - 1} - a_n \end{aligned} \right. \]

然而通过消元法之后可以得到：

$g_3=2ave+g_1-a_1-a_2$

由此，设$x_i=-i*ave +\begin{equation} \sum_{j=1}^{i-1}a_j\end{equation} $

得到$x_i = x_{i-1}-ave+a_i$ -> $g_n = g_1-x_{n-1}$

推得最终式：

$ans=|g_1-0|+|g_1-x_1|+…+|g_1-x_{n-1}|$

又因为当$g_1$为$x[]$的中位数时，ans取得最优解，那么单独求出med，在代入最终式即可。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, a[N];
ll x[N], ans, sum;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    int ave = sum / n;
    for (int i = 1; i <= n; i ++ )
        x[i] = x[i - 1] - a[i] + ave;
    sort(x + 1, x + 1 + n);
    int med = x[n / 2 + 1];
    for (int i = 1; i <= n; i ++ )
        ans += abs(med - x[i]);
    printf("%lld", ans);
    return 0;
}

搬运