洛谷P4016 负载平衡问题 题解

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

题意：

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

输入格式：

第一行一个正整数 \(n\)，表示有 \(n\) 个仓库。

第二行 \(n\) 个正整数，表示 \(n\) 个仓库的库存量。

输出格式：

输出最少搬运量。

数据范围：

\(1 \leq n \leq 100\)。

贪心题写什么网络流。原题：P2512 糖果传递 或者 P2125 图书馆书架上的书。

网上证明很多不写了，可以去看 mygr 巨佬写的文章

贴个 P2125 的代码：（这题要输出传递方案）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))

int sum, mid, a[N], r[N], c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) { cin >> a[i], sum += a[i]; }
    sum /= n; r[0] = c[0] = 0;
    for(int i = 1; i <= n; i++) r[i] = c[i] = c[i - 1] + a[i] - sum;
    sort(c + 1, c + 1 + n); mid = c[(n + 1) / 2]; int res = 0;
    for(int i = 1; i <= n; i++) res += abs(mid - c[i]);
    cout << res << '\n';
    for(int i = 1; i < n; i++)
        cout << mid - r[i - 1] << ' ' << -(mid - r[i]) << '\n';
    cout << mid - r[n - 1] << " " << -mid << '\n';
    return 0;
}

主要是这道题是 网络流24题 系列的，别到时候为了找着这题翻半天。