codeforces 483C.Diverse Permutation 解题报告

题目链接：http://codeforces.com/problemset/problem/483/C

题目意思：给出 n 和 k，要求输出一个含有 n 个数的排列 p1, p2, ...,pn，使得 |p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| 恰好有 k 个不同的数。注意，p1, p2, ..., pn 每个数是不相等的，而且不大于 n。

    构造题，这个通过手动很容易知道答案。又献上我的恶心涂鸦～～～看完之后会发现其实很简单，好像比 B 还要简单。

   

    

     只要红色的竖线前面满足不同的差值恰好有 k 个即可，上面的“+”“-” 是规律来的。竖线后面的差值是清一色等于 1 的。

     

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF)
    {
        if (k == 1)
        {
            for (int i = 1; i <= n; i++)
                printf("%d ", i);
            printf("
");
        }
        else
        {
            printf("1");
            int st = 1;
            int interval = k;
            for (int i = 1; i < k+1; i++, interval--)
            {
                st += (i&1 ? interval : -interval);
                printf(" %d", st);
            }
            for (int i = k+2; i <= n; i++)
                printf(" %d", i);
            printf("
");
        }
    }
    return 0;
}