ACM模版

描述

题解

做这个题真是长见识了，由于序列比较大并且需要生成序列，所以直接快排时间会超，那么怎么做呢？自然是寻求近似线性复杂度的解法了。

官方题解是这么说的：

最慢的情况是  $b$ 的取值为 $0, 1, 2, 3, 5, 8, …$ 的情况，但事实上也只有 $\mathcal{
  O}(\log_{
  1.618}{n})$ 个取值。

从最大的取值到最小的取值依次使用近似线性复杂度的求第 $k$ 小的方法即可，该方法的思想与快排相似，可以保证前 $k - 1$ 小的元素都放置在第 $k$ 小元素的前面，这样枚举的时候就可以依次减少每次的枚举量，时间复杂度 $\displaystyle\mathcal{
  O}\left(\sum_{i \geq 0}{\frac{n}{
  1.618^i}}\right) = \mathcal{
  O}(n)$ 。

这里，用到了一个 STL 函数，很牛逼的一个东西，之前就没有用过，看见标程里用到了，感觉简单快捷，所以找了找这个函数的介绍。

nth_element(a, a + x, a + n);    // 将在 [0 ~ n) 区间的第 x + 1 大的数放置在 x 处， // 小于它的 x 个数放在前边，其余的放后边，无序

这个函数的内部算法和上述的算法相似，时间复杂度也是近似线性的，没毛病。

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e7 + 10;
const int MAXM = 111;

int n, m;
unsigned a[MAXN];
unsigned c[MAXM];

struct xxx
{
    int val, pos;

    bool operator < (const xxx y) const
    {
        return val < y.val;
    }
} b[MAXM];

unsigned x, y, z;
inline unsigned rng61()
{
    unsigned t;
    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;
    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;
    return z;
}

int main()
{
    int ce = 1;
    while (~scanf("%d%d%u%u%u", &n, &m, &x, &y, &z))
    {
        for (int i = 0; i < m; ++i)
        {
            scanf("%d", &b[i].val);
            b[i].pos = i;
        }
        sort(b, b + m);

        for (int i = 0; i < n; ++i)
        {
            a[i] = rng61();
        }

        b[m].val = n;
        for (int i = m - 1; ~i; --i)
        {
            nth_element(a, a + b[i].val, a + b[i + 1].val);
            c[b[i].pos] = a[b[i].val];
        }

        printf("Case #%d: ", ce++);
        for (int i = 0; i < m - 1; ++i)
        {
            printf("%u ", c[i]);
        }
        printf("%u\n", c[m - 1]);
    }

    return 0;
}