P3051 [USACO12MAR]Haybale Restacking G 题解

· · 题解

0. 前言

话说这题有至少四五倍经验啊，结论都一样。 本人太菜了考试的时候没有推出来。 将式子变形竟出现了 \textbf{绝对值不等式}。

1. 翻译

农夫约翰订购了很多干草，他在农场里标记了 N 个位置。这些位置近似地构成一个圆环。他原打算 让送货司机在 i 号位卸下 Bi 捆干草。然而，送货司机搞乱了约翰的部署，胡乱卸货之后就离开了。 约翰数了数，目前在 i 号位有 Ai 捆干草，(题目保证∑Ai=∑Bi）。

无奈之下，农夫约翰只能自己来移动这些干草。但他必须沿相邻位置来移动干草，每移动一捆干草到一个相邻位置，要消耗约翰一单位的能量。请帮约翰规划一下，他最少消耗多少能量才能让所有位置 的干草数量从 Ai 变成 Bi (注意：1 号位和 N 号位也算作是相邻的！）

2. 思路

本题与均分纸牌大体一致，除了变成换无他。 维护 C 数组。内容是 C[i] = B[i] - A[i] + C[i - 1] 可以看出，C[i] 是每一项 B[i] - A[i] 的前缀和。 设 X[i] 为 i 到 i + 1 的移动数量。有通项 X[i] = X[i] + A[1] + A[2] + … + A[i] - B[1] - B[2] - … - B[i]，看到这里就知道前缀和数组的用处了。为使总移动距离最小，使: |Q - C[1]| + |Q - C[2]| + … |Q - C[n]| 最小。\textbf{绝对值不等式} 出现了，只需使 Q 为 C 数组排序后的中位数即可。

3. 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, a[N], b[N], c[N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i] >> b[i];
        c[i] += (b[i] - a[i] + c[i - 1]); 
    }
    sort(c + 1, c + n +1);
    int mid = c[n / 2 + 1];
    long long ans = 0;
    for(int i = 1; i <= n; i ++){
        ans += abs(mid - c[i]);
    }
    cout << ans;
    return 0;
}

非常简短。