win7优化/长沙官网优化公司

https://leetcode-cn.com/problems/random-pick-with-weight/

思路一：随机+二分。首先独立计算出每个数被选中的概率，然后计算该数组的前缀和。那么$a_i$被选中的概率就等于$su{m}_i-su{m}_{i-1}$，且$sum[0..n)=1$。因此每次$pick$可以先计算一个$[0,1]$内的随机数，然后看它落到哪个元素的区间范围内，利用二分可以加速这个过程。

class Solution {
public:Solution(vector<int>& w) {srand(time(NULL));int total=accumulate(w.begin(),w.end(),0);int n=w.size();sum.resize(n);sum[0]=w[0]*1.0/total;for(int i=1;i<n;i++)sum[i]=sum[i-1]+w[i]*1.0/total;}int pickIndex() {float rd=rand()*1.0/RAND_MAX;int l=0,r=sum.size()-1,mid;while(l<=r){mid=(l+r)>>1;if(sum[mid]<rd)l=mid+1;elser=mid-1;}return l;}
private:vector<float> sum;
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(w);* int param_1 = obj->pickIndex();*/

思路二：给每个位置分配一个优先级，然后利用堆来调度。

class node{
public:float val,step;int idx;node(float v,float s,int i):val(v),step(s),idx(i){}bool operator <(const node& a)const{return val>a.val;}
};class Solution {
public:Solution(vector<int>& w) {srand(time(NULL));int total=accumulate(w.begin(),w.end(),0);int n=w.size(),sum=0;for(int i=0;i<n;i++){q.emplace(total*1.0/w[i],total*1.0/w[i],i);}}int pickIndex() {node t=q.top();q.pop();q.emplace(t.val+t.step,t.step,t.idx);return t.idx;}
private:priority_queue<node> q;
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(w);* int param_1 = obj->pickIndex();*/