C. Diverse Permutation（Codeforces Round #275(div2)_html/css_WEB-ITnose

C. Diverse Permutation

time limit per test

memory limit per test

input

output

permutation p is an ordered set of integers p1,???p2,???...,???pn, consisting of n distinct positive integers not larger than n. we'll denote as nthe length of permutation p1,???p2,???...,???pn.

Your task is to find such permutation p of length n, that the group of numbers |p1?-?p2|,?|p2?-?p3|,?...,?|pn?-?1?-?pn| has exactly k distinct elements.

Input

The single line of the input contains two space-separated positive integers n, k (1?≤?k?

Output

Print n integers forming the permutation. If there are multiple answers, print any of them.

Sample test(s)

input

3 2

output

1 3 2

input

3 1

output

1 2 3

input

5 2

output

1 3 2 4 5

Note

By |x| we denote the absolute value of number x.

立即学习“前端免费学习笔记（深入）”；

用n个数1~n，每个数只能用一次，组成差值的绝对值有k个数，为1~k。输出任一个方案。

饭店住房管理服务系统(C#.NET)

饭店住房管理服务系统(C#.NET)

31

查看详情

构造题，我是这样构造的，取前k+1个数，第一个数取1，先+k，后一个数-(k-1),在后一个数+k-2.......这样从两头往

中间靠拢，既取完了k+1个数，又构造了1~k的差值绝对值，至于k+1后的嘛，每次+1就行了。

代码：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn=100000+1000;int ans[maxn];int main(){    int n,k;    ans[1]=1;    scanf("%d%d",&n,&k);    if(k==1)    {        for(int i=1;i<=n;i++)        ans[i]=i;    }    else    {      for(int i=2;i<=k+1;i++)      {        if(i%2)        ans[i]=ans[i-1]-(k-i+2);        else        ans[i]=ans[i-1]+(k-i+2);      }      int cur=1;      for(int i=k+2;i<=n;i++)      {          ans[i]=k+1+cur;          cur++;      }    }    for(int i=1;i<n;i++)    printf("%d ",ans[i]);    printf("%d\n",ans[n]);    return 0;}