codeforces C. Diverse Permutation(构造)

题意：1...n 的全排列中 p1, p2, p3....pn中，找到至少有k个
|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; }

总结

以上是生活随笔为你收集整理的codeforces C. Diverse Permutation(构造)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。