代码

/*
测测你的三维数点3
时间限制： 5 s
空间限制： 2097152 KB

题目描述
三维空间中有 n 个点，每个点分别具有 [0, n) 整数范围的 x 坐标、y 坐标和 z 坐标（不同点的各维坐标值可能重复，即可能存在 x[i] == x[j] 或 y[i] == y[j] 或 z[i] == z[j]）。你需要对每个点，统计每维坐标均小于该点对应维坐标的点的个数。

接口
void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out);

其中，第 i (0 <= i < n) 个点的坐标为 (x[i], y[i], z[i])，其统计结果需要保存到 out[i]。

数据范围
n 等于 10,000
*/

#include <tuple>
#include <vector>

void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
    /*
    for (int i = 0; i < n; i++) {
        out[i] = 0;
        for (int j = 0; j < n; j++) {
            if (x[j] < x[i] && y[j] < y[i] && z[j] < z[i]) {
                out[i]++;
            }
        }
    }
    */
    // 上面的做法太慢了，要 432.134826 ms，我们需要更快的做法
    // 将三维坐标放到同一个 tuple 中，可以加速
    using tuple = std::tuple<unsigned, unsigned, unsigned>;
    std::vector<tuple> v;
    v.reserve(n);
    for (int i = 0; i < n; i++) {
        v.emplace_back(x[i], y[i], z[i]);
    }
    for (int i = 0; i < n; i++) {
        out[i] = 0;
        for (int j = 0; j < n; j++) {
            if (std::get<0>(v[j]) < std::get<0>(v[i]) && std::get<1>(v[j]) < std::get<1>(v[i]) && std::get<2>(v[j]) < std::get<2>(v[i])) {
                out[i]++;
            }
        }
    }
}

评测结果