Codeforces div 863C

Problem - C - Codeforces

设定m=n-1

首先，对于a数组的开头与末尾，我们可以证明，他总是等于b数组的开头和结尾

因为如果$a_2>a_1$ 那么$a_1$也就无法被还原了，所有 { x ∣ x ≤ a 2 } \{x| x\leq a_2\} {x∣x≤a2​}都是成立的，而此时$b_1$是等于$a_2$的，也就保证了$a_1$一定可以等于$b_1$

同理，$a_n=b_m$

解法一

对于b数组中的每个数字，是由a数组中左右两个数字取较大值得到的，通过对$a_1=b_1$ $a_n=b_n-1$ $a_i=min(b_i,b_{i-1})$的实现课复原一个合法的a数组

具体原理如下

考虑一个$1<i<n$的$a_i$

$b_i=max(a_i,a_{i-1})$ $b_{i+1}=max(a_i,a_i+1)$是成立的

我们考虑这样一种情况，也就是$b_i,b_{i-1}$均不是a_i原值的时候，即$a_{i-1}<a_i<a_{i+1}$，此时$a_i$ 无法被还原，也就是说$a_i=min(a_{i-1},a_{i+1})$,即$a_i=min(b_i,b_{i-1})$

对于其他情况，如$b_i==a_i||b_{i-1}==a_i$， 我们直接取两个值当中的最小值就好。因为通过分析可以发现，原来的值一定为较小值

$a_{i-1}<a_i<a_i+1$ 时$b_i=a_i$ $b_{i+1}=a_{i+1}$ 由于$a_i<a_{i+1}$所以$a_i$为其中较小值

由于对称，所以相反的状况下该结论也成立

对于$a_i$在三个值中最大的情况也是成立的因为$b_i=b_i-1=a_i$

所以，对它使用结论吧

inline void slove()
{
    cin >> n;
    m = n - 1;

    for (int i = 1; i <= m; i++) cin >> b[i];

    a[n] = b[m];
    a[1] = b[1];
    for (int i = m; i>1; i--)
        a[i] = min(b[i - 1], b[i]);

    for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
    puts("");

    return;
} 

解法二
其实解法二是对解法一的近似，两者是完全相同的，只不过一个用到了min，另一个没有，不过由于思路的完全不同，这里还是讲一下

从尾遍历，对于每一个$b_i$,如果出现$b_i>b_{i-1}$的情况，需要重复一遍$b_i$，再添加$b_{i-1}$

inline void slove()
{
    cin >> n;
    m = n - 1;

    for (int i = 1; i <= m; i++) cin >> b[i];

    a[n] = b[m];
    a[1] = b[1];
    for (int i = m; i > 1; i--)
    {
        if (b[i - 1] > b[i])
        {
            a[i] = b[i];
            a[i - 1] = b[i - 1];
        }
        else a[i] = b[i - 1];
    }

    for (int i = 1; i <= n; i++) printf("%lld ", a[i]);
    puts("");

    return;
}