search

Home >Web Front-end >HTML Tutorial >Codeforces Round #275 (Div. 2) C Diverse Permutation_html/css_WEB-ITnose

Codeforces Round #275 (Div. 2) C Diverse Permutation_html/css_WEB-ITnose

WBOY
WBOYOriginal
2016-06-24 11:55:311040browse

题目链接：Diverse Permutation



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和k。让找到一种1~n的排列，满足，任意相邻两数之间的差值的绝对值必须为k个不同的值。



解题思路：开始用next_permutation(a, a n)直接生成排列，然后判断，结果TLE到死。暴力枚举搞不定，那只能构造了。详见代码




AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define INF 0x7fffffffint a[100005], b[100005];int main(){//     freopen("in.txt","r",stdin);     int n, k, l, f;    while(scanf("%d%d",&n,&k)!=EOF)    {        f = n - k;                         for(int i=1; i<=f; i++){     //构造n-k个差值为1的序列            printf("%d ", i);        }        f ++;        l = n;        while(f <= l){               //构造差值为2～k的序列            printf("%d ", l--);            if(f <= l)  printf("%d ", f++);            else   break;        }        printf("\n");    }    return 0;}
Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：【】English template Chinese version does not display Chinese_html/css_WEB-ITnoseNext article：【】English template Chinese version does not display Chinese_html/css_WEB-ITnose

Related articles

See more