当前位置:网站首页>Codeforces Round #275 (Div. 2) C – Diverse Permutation (构造)[通俗易懂]

Codeforces Round #275 (Div. 2) C – Diverse Permutation (构造)[通俗易懂]

2022-07-07 20:57:00 全栈程序员站长

大家好,又见面了,我是全栈君。

题目链接:Codeforces Round #275 (Div. 2) C – Diverse Permutation

题意:一串排列1~n。求一个序列当中相邻两项差的绝对值的个数(指绝对值不同的个数)为k个。求序列、

思路:1~k+1。构造序列前段,之后直接输出剩下的数。前面的构造能够依据,两项差的绝对值为1~k构造。

AC代码:

#include <stdio.h>
#include <string.h>
int ans[200010];
bool vis[100010];
int n,mark;
int iabs(int a)
{
    if(a<0) return -a;
    return a;
}
int main()
{
    int i,cnt,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        int x,y;
        memset(vis,0,sizeof vis);
        ans[0]=1;
        x=1,y=k+1;
        cnt=k;
        for(i=1; i<=k; i++,cnt--)
        {
            int temp=ans[i-1]+cnt;
            if(temp>k+1)
                temp=ans[i-1]-cnt;
            else if(vis[temp])
                temp=ans[i-1]-cnt;
            ans[i]=temp;
            vis[temp]=true;
        }
        for(i=k+1; i<n; i++)
            ans[i]=i+1;
        for(i=0; i<n-1; i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[i]);
    }
    return 0;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116287.html原文链接:https://javaforall.cn

原网站

版权声明
本文为[全栈程序员站长]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/2043304