首页 > 代码库 > Codeforces 482A Diverse Permutation(构造)

Codeforces 482A Diverse Permutation(构造)

题目链接:Codeforces 482A Diverse Permutation

题目大意:给定N和K,即有一个1~N的序列,现在要求找到一个排序,使得说所有的|pi?pi+1|的值有确定K种不同。

解题思路:构造,1,K+1,2,K,3,K-1,... K+2,K+3 ... N。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 5;

int N, K, arr[maxn], vis[maxn];

int main () {
    scanf("%d%d", &N, &K);

    int u = 1, s = 1, t = K, mv = 1;

    while (t) {
        arr[mv++] = u;
        u = u + s * t;
        s *= -1;
        t--;
    }
    arr[mv++] = u;
    for (int i = K + 2; i <= N; i++)
        arr[i] = i;


    for (int i = 1; i <= N; i++)
        printf("%d%c", arr[i], i == N ? ‘\n‘ : ‘ ‘);
    return 0;
}

Codeforces 482A Diverse Permutation(构造)