ACM模版

描述

题解

这个题实际上就是一个排序，然后暴力查找就好了，复杂度看似高，其实最坏情况下的复杂度为： nlogn+n/2+n/3+n/4+…+n/n ，也就是 nlogn 。

然而一开始我将这个题想难了……以为是一个线段树求区间最值的题……折腾好久。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

struct node
{
    int num, pos;
} A[MAXN];

bool cmp(node x, node y)
{
    return x.num > y.num;
}

int n;

int solve(int x)
{
    int tmp = 1;
    while (A[tmp].pos % x == 0)
    {
        tmp++;
    }
    return A[tmp].num;
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(n);
        for (int i = 1; i <= n; i++)
        {
            scan_d(A[i].num);
            A[i].pos = i;
        }

        sort(A + 1, A + 1 + n, cmp);

        for (int i = 2; i <= n; i++)
        {
            printf("%d%c", solve(i), i == n ? '\n' : ' ');
        }
    }

    return  0;
}