CF2171B Yuu Koito and Minimum Absolute Sum

Andy1101 · 2025-12-01 12:23:18 · 题解

题目传送门

题目大意

定义一个数组 b_i=a_{i+1}-a_i。你需要用非负整数替换 a 数组中的所有 -1，使得在 \sum\limits_{i=1}^{n-1}b_i 的绝对值最小的前提下让数组 a 的字典序最小。即在 \left|b_1+b_2+ \dots b_{n-2}+b_{n-1}\right| 最小的前提下让数组 a 的字典序最小。

思路

因为 b_1=a_2-a_1 \ ,\ b_2=a_3-a_2 \ ,\ b_3=a_4-a_3 \ ,\ \dots \ ,\ b_{n-2}=a_{n-1}-a_{n-2} \ ,\ b_{n-1}=a_n-a_{n-1}，所以我们可以看出 \sum\limits_{i=1}^{n-1}b_i=a_n-a_1。也就是说答案只与 a_n 和 a_1 有关，而且为了保证字典序最小，将其余的未知数都赋值为 0 即可。这时候我们就可以分成四种情况来讨论。

1. 当 a_1 和 a_n 都未知时，将 a_1 和 a_n 都赋值为 0（因为要保证字典序最小，所以要赋值为 0），最小值为 0。
2. 当 a_1 未知，a_n 已知时，将 a_1 赋值为 a_n 的值，最小值为 0。
3. 当 a_1 已知，a_n 未知时，将 a_n 赋值为 a_1 的值，最小值为 0。
4. 当 a_1 和 a_n 都已知时，最小值为 \left|a_n-a_1\right|。

随后输出数组 a 即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+4;
int a[N]; 
void solve()
{
    int n;
    cin >>n;
    for(int i=1;i<=n;i++) cin >>a[i];
    if(a[1]!=-1 && a[n]!=-1)
    {
        cout <<abs(a[n]-a[1])<<'\n'; 
        for(int i=1;i<=n;i++)
        {
            if(a[i]==-1) cout <<0<<" ";
            else cout <<a[i]<<" ";
        }
    }
    else if(a[1]==-1 && a[n]!=-1)
    {
        cout <<0<<'\n';
        for(int i=1;i<=n;i++)
        {
            if(i==1) cout <<a[n]<<" ";
            else if(a[i]==-1) cout <<0<<' ';
            else cout <<a[i]<<' ';
        }
    }
    else if(a[1]!=-1 && a[n]==-1)
    {
        cout <<0<<'\n';
        for(int i=1;i<=n;i++)
        {
            if(i==n) cout <<a[1]<<" ";
            else if(a[i]==-1) cout <<0<<" ";
            else cout <<a[i]<<" ";
        }
    }
    else
    {
        cout <<0<<"\n";
        for(int i=1;i<=n;i++)
        {
            if(a[i]==-1) cout <<0<<" ";
            else cout <<a[i]<<" ";
        }
    }
    cout <<'\n';
}
int main()
{

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