# LeetCode - 0528. Random Pick with Weight
### 題目網址：https://leetcode.com/problems/random-pick-with-weight/
###### tags: `LeetCode` `Medium` `數學` `機率`

/*
    -LeetCode format-
    Problem: 528. Random Pick with Weight
    Difficulty: Medium
    
    by Inversionpeter
*/



int prefixSums[10001], amount, total, upperbound;

class Solution {
public:
    Solution(vector<int>& w) {
        srand(time(nullptr));
        amount = w.size();
        for (int i = 0; i < amount; ++i)
            prefixSums[i + 1] = prefixSums[i] + w[i];
        total = prefixSums[w.size()];
        upperbound = (RAND_MAX / total) * total;
    }
    
    int pickIndex() {
        static int weight;
        do {
            weight = rand();
        } while (weight >= upperbound);
        weight %= total;
        return int(upper_bound(prefixSums, prefixSums + amount, weight) - prefixSums) - 1;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */