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;
}


目录
相关文章
|
6月前
|
搜索推荐 C++
[C++/PTA] 有序数组(类模板)
[C++/PTA] 有序数组(类模板)
54 0
|
网络架构
Codeforces Round #755 D. Guess the Permutation(交互 二分)
Codeforces Round #755 D. Guess the Permutation(交互 二分)
90 0
|
人工智能
CF1315 C.Restoring Permutation(构造 二分 贪心)
CF1315 C.Restoring Permutation(构造 二分 贪心)
68 0
|
Perl
Codeforces 1312E. Array Shrinking(区间DP 栈)
Codeforces 1312E. Array Shrinking(区间DP 栈)
96 0
|
人工智能
[Codeforces 1286B] Numbers on Tree | 技巧构造
Evlampiy was gifted a rooted tree. The vertices of the tree are numbered from 1 to n. Each of its vertices also has an integer ai written on it. For each vertex i, Evlampiy calculated ci — the number of vertices j in the subtree of vertex i, such that a j < a i
115 0
[Codeforces 1286B] Numbers on Tree | 技巧构造
|
人工智能
Codeforces 220B-Little Elephant and Array-扫描线 & 树状数组
题意: 给出一个长度为n的数组,有m个询问,每次询问给出一个区间,问这个区间内有多少个数x恰好出现x次
126 0
Codeforces 220B-Little Elephant and Array-扫描线 & 树状数组
|
人工智能 算法 C#
算法题丨Next Permutation
描述 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
1332 0