洛谷 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

11

题解:

这道题大致的思路是贪心+数学(虽然某谷标签是网络流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;
}
01-02 15:45