题解：CF549G Happy Line

dengrunze2608 · 2025-08-17 09:25:07 · 题解

题意

给定一个长度为 n 的整数序列 a。对于任意一对相邻元素 (a_{i-1},a_i)，若 a_{i-1}>a_i，则可以执行以下操作：

2. 交换 a_{i-1} 和 a_i 的位置。

思路

通过分析可以发现，每次操作虽然会改变元素的 值和位置，但每个元素的 a[i]+i 的值始终保持不变。

这样我们可以将问题转化为对辅助数组 b[i]=a[i]+i 的排序问题：首先计算 a 数组每个元素的 a[i]+i 的值存入 b 数组并排序，然后通过 a[i]=b[i]-i 还原出最终序列，这样得到的序列自然满足操作后的数值关系。

但还需要验证两个关键条件：

1. 所有还原后的元素必须非负。

2. 还原后的序列必须是非降的。

如果这两个条件都满足，则输出最终序列。否则说明无法通过操作使序列有序，输出 :(。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N],n;
int main(){
    cin>>n; 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]+i;//计算辅助数组。
    }
    sort(b+1,b+n+1);//排序辅助数组。
    for(int i=1;i<=n;i++){
        a[i]=b[i]-i;//计算最终序列。
        //检查是否非负且非降。
        if(a[i]<0||(i>1&&a[i]<a[i-1])){
            cout<<":(";
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}