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?<?n ?≤?105).
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