随机数的应用：广告投放

题目&＃xff1a;
网站有一个展示广告的区域&＃xff0c;每次同时展示2个不同的广告素材&＃xff0c;现有N个广告素材及每个广告出现的权重std::vector weights[N]; weight[i]代表第i个广告权重。实现该广告展示函数。
例如weights[]&＃61;{1,2,3,4};则总权重是10,0号广告素材出现概率是1/10,1号是2/10…
如果运行1000万次该函数&＃xff0c;则统计后0号广告出现200万次左右&＃xff0c;1号400万次左右…(每次返回2个广告所以统计次数是2000万次&＃xff09;

说明: 
1.为了保证用户新鲜感&＃xff0c;算法需要保证每一种组合都有出现的可能。不能按固定组合依次输出。
2.每次返回2个不同的&＃xff0c;请务必保证&＃xff01;
3.随机函数为: int rand(void);
4.可以额外填加全局变量、函数和main函数中的代码。

分析&＃xff1a;
随机数生成的区间是权重之和&＃xff0c;所以我们可以预处理前缀和&＃xff0c;用于判断产生的随机数具体落在哪个区间&＃xff0c;这里用的是O(n)的枚举&＃xff0c;n是广告个数&＃xff0c;想要更快可以使用二分或者hash。

代码&＃xff1a;

#include
#include
#include
#include
using namespace std;int ads_num; //广告素材的数量
vector weights;//每个广告素材的权重
int f[1000]; //权重前缀和
int sum; void genAdvertiseItem(int &first, int& second) {int x&＃61;rand()%sum;int i&＃61;ads_num-1;while (f[i]>x) i--;first&＃61;i;x&＃61;rand()%sum;i&＃61;ads_num-1;while (f[i]>x) i--;second&＃61;i;
}
int main(){cin>>ads_num;for (int i&＃61;1; i<&＃61;ads_num; i&＃43;&＃43;){int x;cin>>x;sum&＃43;&＃61;x;f[i]&＃61;f[i-1]&＃43;x; weights.push_back(x);} srand(time(0));int first,second;int* counter &＃61; new int[ads_num](); //每个的出现次数for(int i&＃61;0;i<10000000;i&＃43;&＃43;){genAdvertiseItem(first,second);counter[first]&＃43;&＃43;;counter[second]&＃43;&＃43;;}for(int i&＃61;0;i}