题解：CF2013D Minimize the Difference

wuxigk · 2024-11-27 19:49:56 · 题解

前言

搜了一圈都没有看到对“最小极差等于最大后缀平均值向上取整减去最小前缀平均值向下取整”这一结论的证明，因此在这里补一个。证明过程还是有一定的技巧性的，尤其是引理二，其中用到了一些取整函数的性质，不熟悉的同学可以自行了解。

一些记号

对于长度为 n 的序列 A，记：

• 下标为 1\sim n 组成的连续子序列为 A_{1\sim n}；

• 若 A_i>A_{i+1}，称 (i,i+1) 上的操作是“平衡”的。

引理一

对序列 A 进行任意次操作得到序列 B， 则 \min(B)\le\lfloor L(A)\rfloor且\max(B)\ge\lceil R(A)\rceil。

引理一证明

记序列长度为 n，假设 \min(B)>\lfloor L(A)\rfloor。令 i 为某个满足 L(A,i)=L(A) 的正整数，因为 L(B,i)\ge\min(B)，故：

因此 L(B,i)>L(A,i)，即 S(B_{1\sim i})>S(A_{1\sim i})。

然而，\forall j\ne i，在 (j,j+1) 上进行的操作不会影响 S(B_{1\sim i})，而在 (i,i+1) 上进行的操作使得 S(B_{1\sim i}) 变小，因此最终一定有 S(B_{1\sim i})\le S(A_{1\sim i})，矛盾。

对于后缀平均值的命题同理可证。

引理二

对序列 A 进行任意次平衡操作得到序列 B，则 \lfloor L(A)\rfloor=\lfloor L(B)\rfloor 且 \lceil R(A)\rceil=\lceil R(B)\rceil。

引理二证明

只需证明命题对单次平衡操作成立，记该平衡操作在 (i,i+1) 上进行。不难发现，\forall j\ne i,L(A,j)=L(B,j)，而 L(B,i)=L(A,i)-\frac{1}{i}<L(A,i)，因此 L(B)\le L(A)，所以 \lfloor L(B)\rfloor\le\lfloor L(A)\rfloor，下面证明一定取等。

假设 \lfloor L(B)\rfloor<\lfloor L(A)\rfloor，则 \forall j\ne i,\lfloor L(B,i)\rfloor<\lfloor L(B,j)\rfloor。（否则 \exists k\ne i,\lfloor L(B)\rfloor=\lfloor L(B,k)\rfloor=\lfloor L(A,k)\rfloor\ge\lfloor L(A)\rfloor，矛盾）

若 i=1 ，则 \lfloor L(B,1)\rfloor<\lfloor L(B,2)\rfloor，即 A_1-1<\left\lfloor\frac{A_1+A_2}{2}\right\rfloor。讨论 A_2 的大小：若 A_2\le A_1-2，则 \left\lfloor\frac{A_1+A_2}{2}\right\rfloor\le A_1-1，矛盾；若 A_2=A_1-1，则 \left\lfloor\frac{A_1+A_2}{2}\right\rfloor= A_1-1，亦矛盾。

若 i>1 ，一方面有 \lfloor L(B,i)\rfloor<\lfloor L(B,i-1)\rfloor，因此 L(B,i)<L(B,i-1)，展开并整理得到：

另一方面，对 L(B,i) 与 L(B,i+1) 作差，利用 A_{i+1}\le A_i-1 以及前面的不等式整理得到：

将不等式左边拆成“整数部分加小数部分”的形式，整理得到：

其中 \lfloor L(B,i+1)\rfloor-\lfloor L(B,i)\rfloor\ge 1,\{L(B,i+1)\}\ge 0，因此 \{L(B,i)\}>\frac{i}{i+1}。但 L(B,i) 可表示为分母为 i 的有理数，因此 \{L(B,i)\}\le\frac{i-1}{i}，矛盾。

综上，一定有 \lfloor L(A)\rfloor=\lfloor L(B)\rfloor，同理可证明 \lceil R(A)\rceil=\lceil R(B)\rceil。

最优解的构造及证明

对于长度为 n 的序列 A，在其上反复使用平衡操作，直到得到单调不减的序列 B。由于 B 单调不减，显然有 \min(B)=B_1=L(B)=\lfloor L(B)\rfloor 以及 \max(B)=B_n=R(B)=\lceil R(B)\rceil。根据引理二，\lfloor L(B)\rfloor=\lfloor L(A)\rfloor 且 \lceil R(B)\rceil=\lceil R(A)\rceil，因此序列 B 的极差 \max(B)-\min(B)=\lceil R(A)\rceil-\lfloor L(A)\rfloor。

另一方面，根据引理一，无论在 A 上进行怎样的操作，最终得到的序列 C 一定满足 \max(C)-\min(C)\ge\lceil R(A)\rceil-\lfloor L(A)\rfloor，因此上述序列 B 已经达到了最优解，故最终答案为 \lceil R(A)\rceil-\lfloor L(A)\rfloor。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for (auto& x : a)
            cin >> x;
        vector<ll> pre_avg(n), suf_avg(n);
        pre_avg[0] = a[0];
        for (int i = 1; i < n; i++)
            pre_avg[i] = pre_avg[i - 1] + a[i];
        for (int i = 0; i < n; i++)
            pre_avg[i] /= i + 1;
        suf_avg[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--)
            suf_avg[i] = suf_avg[i + 1] + a[i];
        for (int i = n - 1; i >= 0; i--)
            suf_avg[i] = (suf_avg[i] + n - i - 1) / (n - i);
        cout << *ranges::max_element(suf_avg) - *ranges::min_element(pre_avg) << '\n';
    }
}