Codeforces Round #275 (Div. 2) C

Question link: Codeforces Round #275 (Div. 2) C - Diverse Permutation

Question meaning: A series of arrangements 1~n. Find the number of absolute values ​​of the differences between adjacent two items in a sequence (referring to the number of different absolute values) to be k. Find the sequence,

Idea: 1~k 1. Construct the first part of the sequence, and then directly output the remaining numbers. The previous construction can be constructed based on the fact that the absolute value of the difference between the two terms is 1~k.

AC code:

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