首页 > 代码库 > codeforces C. Diverse Permutation(构造)

codeforces C. Diverse Permutation(构造)

2024-07-29 04:29:36   220人阅读

题意：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 }
View Code

 

codeforces C. Diverse Permutation(构造)


联系
我们