当前位置:Gxlcms > html代码 > C.DiversePermutation(CodeforcesRound#275(div2)_html/css_WEB-ITnose

C.DiversePermutation(CodeforcesRound#275(div2)_html/css_WEB-ITnose

时间:2021-07-01 10:21:17 帮助过:32人阅读

C. Diverse Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard 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。输出任一个方案。

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

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

代码:

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

人气教程排行