主要思路

这道题是数学推理的好题。

我们考虑把所有的移动全部作为单向移动，设\(x_i\)为\(i\)向\(i – 1\)移动书本的数量。显然，如果我们要把书向右移动，那么我们就把\(x_{i + 1}\)减去相应的值即可。

接下来进行推理。考虑总的答案为：\(\sum_{i = 1}^n |x_i|\)。我们要最小化这个东西。为了简化这个东西，我们可以注意到其中\(x_i\)中隐藏的递推的性质：

\[ \begin{cases} a_1 = avg – x_2 + x_1 \\ a_2 = avg – x_3 + x_2 \\ \dots \end{cases} \]

我们可以常数固定\(x_1\)，进行移项和代换：

\[ x_2 = avg – a_1 + x_1 \\ x_3 = avg – a_2 + x_2 = 2avg – a_2 – a_1 + x_1 = x_1 – (a_1 + a_2 – 2avg) \\ x_n = x_1 – (\sum_{i = 1}^{n – 1} a_i – (n – 1) \times avg) \]

发现后面的求和可以递推（\(c_i = c_{i – 1} + a_i – avg\)）现在变成：

\[\sum_{i = 1}^n |x_i| = |x_1 – c_1| + |x_1 – c_2| \dots \]

货仓选址，然后还原即可。

代码

// P2125.cpp
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int MAX_N = 5001001;

ll sum, ai[MAX_N], n, ci[MAX_N], x1, org[MAX_N];

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &ai[i]), sum += ai[i];
    sum /= n;
    for (int i = 1; i <= n; i++)
        ci[i] = org[i] = ci[i - 1] + ai[i] - sum;
    nth_element(ci + 1, ci + (n >> 1) + 1, ci + 1 + n), x1 = ci[(n >> 1) + 1];
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += llabs(ci[i] - x1);
    printf("%lld\n", ans);
    for (int i = 1; i < n; i++)
        printf("%lld %lld\n", x1 - org[i - 1], -(x1 - org[i]));
    printf("%lld %lld\n", x1 - org[n - 1], -x1);
    return 0;
}