题目描述
官方描述(中文)
2021/08/30每日一题
思路
说实话看到题,我毫无思路。。。只能去翻一下官方题解,官方题解。官方题解使用到了好几个非常不常用的stl类(至少对于我来说非常不常用,基本没用过。。。):
- mt19937 随机数类
- uniform_int_distribution均匀离散分布类
- random_device 随机数类
还有几个不常用的函数
- accumulate 求取指定范围的数据和
- partial_sum 求取指定范围的前缀和放入指定容器
- lower_bound 某一数在指定范围中第一个大于等于这个数的位置
代码
直接扣的官方代码
class Solution
{
private:
mt19937 gen;
uniform_int_distribution<int> dis;
vector<int> pre;
public:
/*
partial_sum() 可以计算输入序列中元素的部分和,并将结果保存到一个输出序列中
back_inserter 是iterator适配器,它使得元素被插入到作为实参的某种容器的尾部
random_device提供()操作符,用来返回一个min()到max()之间的一个数字
*/
//给随机数gen设置随机种子,accumulate求取w中所有数字的和,dis为0-sum(w)的均匀离散分布
Solution(vector<int>& w): gen(random_device{}()), dis(1, accumulate(w.begin(), w.end(), 0))
{
//求取w的前缀和并将结果存储在pre中
partial_sum(w.begin(), w.end(), back_inserter(pre));
}
int pickIndex()
{
//得到0-sum(w)之间的随机数
int x = dis(gen);
//得到随机数x在pre中的位置
return lower_bound(pre.begin(), pre.end(), x) - pre.begin();
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(w);
* int param_1 = obj->pickIndex();
*/
Q.E.D.