[CF 549G] Happy Line

作法：

這題只要觀察到：當$a_i$和$a_{i+1}$交換時，所有數形成的$i+a_i$的集合都不會變，因為當交換時這兩數的$i+a_i$值是從$(i+a_i,i+1+a_{i+1})$變成$((a_{i+1}+1)+i,(a_i-1)+i+1)$ 。並且顯然這是充要的，也就是如果兩數列的$i+a_i$集合相同，那麼就可以把一個變成另一個（只要一個一個放到對的位子就好了）。所以現在有了$i+a_i$的集合，我們想要讓$a_1,...,a_n$是遞增的，那麼$a_1$的值越小越好，那麼就取$i+a_i$集合裡最小的那個數扣掉$1$就是所求的$a_1$了，這樣取會是最好的。同理$a_2$會取集合裡第二小的數，以此類推。因此只要按照$i+a_i$值排序就可以找出解了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
int a[maxn],ans[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , a[i]+=i ;
    sort(a+1,a+n+1) ;
    for(int i=1;i<=n;i++)
    {
        ans[i]=a[i]-i ;
        if(i>1 && ans[i]<ans[i-1]){printf(":(\n") ; return 0 ;}
    }
    for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ') ;
}