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