首页 > 代码库 > Codeforces 482 - Diverse Permutation 构造题

Codeforces 482 - Diverse Permutation 构造题

这是一道蛮基础的构造题。

           - k         +(k - 1)      -(k - 2) 

1 + k ,    1 ,         k ,             2,    ...................

         \  /        \  /           \  /

          k          k-1          k-2

如图所示,先构造第一个数,就是1 + k, 然后接下来每个数字和上个数相差k , k -1 , k -2

这样下来,最后一个数字就是一个中间的数字,过程就是不断向中间逼近。

在k + 1后面的数字,只要升序输出就可以了。

 

构造题还是不太熟练阿 QAQ

贴代码了:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;int a[100001];int main(){    int i, j, k, t, m, n;    while(EOF != scanf("%d%d",&n,&k)){        if(k == 1){            for(i = 1; i < n; ++i)  printf("%d ",i);            printf("%d\n",n);            continue;        }        a[1] = 1 + k;        for(i = 2; i <= k + 1; ++i){            if(i % 2 == 0)                a[i] = a[i - 1] - (k - (i - 2));            else                a[i] = a[i - 1] + (k - (i - 2));        }        int cur = 1;        for(i = k + 2; i <= n; ++i){            a[i] = k + 1 + cur++;        }        for(i = 1; i < n; ++i){            printf("%d ",a[i]);        }        printf("%d\n",a[n]);    }    return 0;}

 

Codeforces 482 - Diverse Permutation 构造题