C++ Random Pick with Weight

在做五子棋 AI 的时候，遇到要根据权重从一组数里边选出一个这个问题。这个问题恰好也是 leetcode 第 528 道题，可以自己写算法解题，幸运的是，标准库就有这个功能：

#include <random>int random_pick(double const* w, int k) {std::random_device rd;return std::discrete_distribution<int>{w, w+k}(rd);
}

自己写大概如下：

#include <numeric>
#include <random>
#include <algorithm>int random_pick(double const* w, int k) {double *sum = (double*)alloca(k*sizeof(double)); //stack allocationstd::partial_sum(w, w+k, sum);std::random_device rd;std::uniform_real_distribution<double> rnd(0, sum[k-1]);return std::upper_bound(sum, sum+k, rnd(rd)) - sum;
}