CF549G Happy Line

解题思路

题意大概就是给你个数列，你可以随意交换i,i+1,交换后位于第i+1位的数字+1，位于第i位的数字-1，问最终能否形成一个不下降序列并输出。设初始数列中两个位置x,y最终交换后的位置为u,v（u

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 200005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

struct Data{

    int a,id;

}data[MAXN];

inline bool cmp(Data A,Data B){

    return A.a+A.id<B.a+B.id;

}

int n;

int ans[MAXN];

int main(){

    n=rd();

    for(register int i=1;i<=n;i++) data[i].a=rd(),data[i].id=i;

    sort(data+1,data+1+n,cmp);

    for(register int i=1;i<=n;i++){

        ans[i]=data[i].a+(data[i].id-i);

//      cout<<ans[i]<<" ";

        if(ans[i]<ans[i-1]) {

            puts(":(");

            return 0;

        }

    }

    for(register int i=1;i<=n;i++)

        printf("%d ",ans[i]);

    return 0;

}

巴特西

CF549G Happy Line

解题思路

代码

最新文章

热门文章