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
Release: 2016-06-24 11:55:31
Original
1045 people have browsed it

题目链接: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
Copy after login

output

1 3 2
Copy after login

input

3 1
Copy after login

output

1 2 3
Copy after login

input

5 2
Copy after login

output

1 3 2 4 5
Copy after login

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



source:php.cn
Statement of this Website
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
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template