题解：CF2171B Yuu Koito and Minimum Absolute Sum

· · 题解

题目分析

有一个数组 a ，其中某些位置是 -1（表示未填充），要求用非负整数填充这些位置，使得差分数组 b 的元素之和的绝对值最小：

S \gets \left| \sum_{i\gets1}^{n-1} b_i \right| \gets \left| \sum_{i\gets1}^{n-1} (a_{i+1} - a_i) \right|

注意这个求和可以化简：

\sum_{i\gets1}^{n-1} (a_{i+1} - a_i) \gets a_n - a_1

所以，题目实际上是在问：能否通过选择非负整数填充 -1 的位置，使得 |a_n - a_1| 最小，并且在最小化这个差值的同时，让整个数组字典序最小。

::::info[注意]

最小化 |a_n - a_1|

  1. 如果 a_1 和 a_n 都已知，那么 S \gets |a_n - a_1| 已固定。
  2. 如果 a_1 已知， a_n 未知，我们可以选 a_n \gets a_1 使 S \gets 0 （因为 a_n 可以是非负整数）。
  3. 如果 a_n 已知， a_1 未知，可以选 a_1 \gets a_n 使 S \gets 0 。
  4. 如果两者都未知，我们可以选 a_1 \gets a_n \gets 0 使 S \gets 0 。
  5. 但注意：我们填充时，所有元素必须是非负整数。

因此：

所以最小可能的 S 是：

S_{\min} \gets \begin{cases} 0 & \text{如果 } a_1 \gets -1 \text{ 或 } a_n \gets -1 \\ |a_n - a_1| & \text{否则} \end{cases}

字典序最小

在 S 最小化后，还需要让整个数组字典序最小。

令 S \gets 0 ，即 a_1 \gets a_n 。

为了字典序最小：

然后中间的元素：我们填充 -1 时，要保证非负整数，并且字典序最小。
对于每个 -1，我们可以填 0，除非它前面有固定值 a_{i-1} 且后面有固定值 a_{i+1} ，这时我们可能需要调整以保持 S \gets 0 吗？
不，因为中间值不影响 S ，所以为了字典序最小，所有未知中间元素直接填 0 即可。

但是：我们必须保证所有 a_i 是非负整数，并且中间填充时，如果相邻元素是固定值，填 0 可能比它们小，但这样是允许的，因为非负整数包括 0，并且不会影响 S 。

因此，策略是：

  1. 确定 a_1 和 a_n 的值（使它们相等，用已知值或 0）。
  2. 对于其他 -1，填 0。
  3. 如果某位置已知，就保持原值。

情况 2： a_1 和 a_n 都已知且不同

此时 S_{\min} \gets |a_n - a_1| 固定。
我们无法改变 a_1 和 a_n ，但中间元素可以自由选择（非负整数）来让字典序最小。

同样，中间未知元素直接填 0 即可（因为填更小的数不会破坏任何条件，且字典序更小）。

算法实现

如果 a_0 = -1 或 a_{n-1} = -1：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;

int a[N];
void solve() {
    int n;
    cin >> n;
    for(int i = 0;i < n + 10;i++){
        a[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (a[0] == -1) {
        if (a[n-1] == -1) {
            a[0] = 0;
            a[n-1] = 0;
        } else {
            a[0] = a[n-1];
        }
    } else {
        if (a[n-1] == -1) {
            a[n-1] = a[0];
        }
    }

    int minn;
    if (a[0] == -1 || a[n-1] == -1) {
        minn = 0;
    } else {
        minn = abs(a[n-1] - a[0]);
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == -1) {
            a[i] = 0;
        }
    }

    cout << minn << "\n";
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << '\n';
}

int main() {   
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

AC记录。