题意:1...n 的全排列中 p1, p2, p3....pn中,找到至少有k个
|p1-p2| , |p2-p3|, ...|pn-1 - pn| 互不相同的元素!
思路: 保证相邻的两个数的差值的绝对值为单调递减序列.....
|p1-p2| , |p2-p3|, ...|pn-1 - pn| 互不相同的元素!
思路: 保证相邻的两个数的差值的绝对值为单调递减序列.....
如果够k个了,最后将没有访问到的元素直接添加到末尾!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
int vis[N];
int num[N];
int main(){
int n, k;
scanf("%d%d", &n, &k);
num[1] = 1;
vis[1] = 1;
int c = k, i;
for(i=2; i<=n; ++i){
if(num[i-1]-c >0 && !vis[num[i-1]-c]){
vis[num[i-1]-c]=1;
num[i] = num[i-1]-c;
}
else if(num[i-1]+c <= n && !vis[num[i-1]+c]){
vis[num[i-1]+c]=1;
num[i] = num[i-1]+c;
}
--c;
if(c < 1) break;
}
for(int j=1; j<=n; ++j)
if(!vis[j]) num[++i]=j;
printf("%d", num[1]);
for(int j=2; j<=n; ++j)
printf(" %d", num[j]);
printf("\n");
return 0;
}