首页 > 代码库 > codeforces C. Diverse Permutation(构造)
codeforces C. Diverse Permutation(构造)
题意:1...n 的全排列中 p1, p2, p3....pn中,找到至少有k个
|p1-p2| , |p2-p3|, ...|pn-1 - pn| 互不相同的元素!
思路: 保证相邻的两个数的差值的绝对值为单调递减序列.....
如果够k个了,最后将没有访问到的元素直接添加到末尾!
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 6 #define N 100005 7 using namespace std; 8 9 int vis[N];10 int num[N];11 int main(){12 int n, k;13 scanf("%d%d", &n, &k);14 num[1] = 1;15 vis[1] = 1;16 int c = k, i;17 for(i=2; i<=n; ++i){18 if(num[i-1]-c >0 && !vis[num[i-1]-c]){19 vis[num[i-1]-c]=1;20 num[i] = num[i-1]-c;21 }22 else if(num[i-1]+c <= n && !vis[num[i-1]+c]){23 vis[num[i-1]+c]=1;24 num[i] = num[i-1]+c;25 }26 --c;27 if(c < 1) break;28 }29 for(int j=1; j<=n; ++j)30 if(!vis[j]) num[++i]=j;31 printf("%d", num[1]);32 for(int j=2; j<=n; ++j)33 printf(" %d", num[j]);34 printf("\n");35 return 0;36 }
codeforces C. Diverse Permutation(构造)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。