[CF549G] Happy Line - 结论

Description

给定一个 n 个元素的整数序列 a[], 任意时刻对于任一对相邻元素 a[i-1]、a[i]，若 a[i-1] < a[i] 则要依次执行如下两个操作：a[i-1]--, a[i]++，交换 a[i-1] 和 a[i] 的位置。经过若干次1、2操作后，若能使整个序列变成非降的，则输出最终的序列；否则输出"??"。

Solution

在整个变换过程中，ai+i 是保持不变的

设 bi=ai+i

那么就转化为了，b[i-1]<=b[i] 时，两个数会交换，仅此而已

当然，bi-1=bi 时交换与否不影响最终结果

所以我们算出 bi 排个序，然后检查是否满足条件即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i], a[i] += i;
    sort(a.begin(), a.end());
    for (int i = 1; i < n; i++)
        if (a[i - 1] >= a[i])
        {
            cout << ":(";
            return 0;
        }
    for (int i = 0; i < n; i++)
        cout << a[i] - i << " ";
}

[CF549G] Happy Line - 结论