Codeforces Round #275 (Div. 2) C - Diverse Permutation (构造)
阅读原文时间:2020年09月28日阅读:1

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

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

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

AC代码:

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

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章