自动搬运

查看原文

来自洛谷，原作者为

	Altwilio AFO|兰花指捻红尘似水

搬运于2025-08-24 21:44:47，当前版本为作者最后更新于2022-02-23 13:24:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$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;
}

非常简短。