题意

给定一个长度为

n

的整数序列

a

。对于任意一对相邻元素

(a_{i-1},a_i)

，若

a_{i-1}>a_i

，则可以执行以下操作：

$a_{i-1}$ 减 $1$ ， $a_i$ 加 $1$ 。
交换 $a_{i-1}$ 和 $a_i$ 的位置。

思路

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

这样我们可以将问题转化为对辅助数组 b[i]=a[i]+i 的排序问题：首先计算

a

数组每个元素的

a[i]+i

的值存入

b

数组并排序，然后通过 a[i]=b[i]-i 还原出最终序列，这样得到的序列自然满足操作后的数值关系。

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

所有还原后的元素必须非负。
还原后的序列必须是非降的。

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

代码

CPP

#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;
}

题解：CF549G Happy Line

文章操作

题意

思路

代码

相关推荐

评论

题解：CF549G Happy Line