红包算法
微信抢红包想来大家都知道，发出一个固定金额的红包，由若干个人来抢，需要满足哪些规则？
- 所有人抢到金额之和等于红包金额，不能超过，也不能少于。
- 每个人至少抢到一分钱。
- 要保证所有人抢到金额的几率相等。
普通法：每次针对剩余总金额做一次随机，随机值就是第一个人的数值。这个算法的好处是完全随机，坏处是极有可能造成前人抢的太多，后人太少。例如，100元分给10个人，第一个人在0-100随机，均值为50。而第二个人的均值只剩25，之后是12.5。
普通法和二倍均值法各有缺点，来看看《算法之旅》中提到的没有实现的线段切割法。
线段切割法
把红包总金额M想象成一条很长的线段，而每个人抢到的金额，则是这条主线段所拆分出的若干子线段。
每个人抢到的金额也就是子线段的长度由“切割点”来决定。当 N 个人一起抢红包的时候，就需要确定 N-1 个切割点。因此，我们需要做 N-1 次随机运算，以此确定 N-1 个切割点。随机的范围区间是（1， M-1）。
当所有切割点确定以后，子线段的长度也随之确定。这样每个人来抢红包的时候，只需要顺次领取与子线段长度等价的红包金额即可。
这就是线段切割法的思路。在这里需要注意以下两点：
- 当随机切割点出现重复，如何处理。
- 如何尽可能降低时间复杂度和空间复杂度。
#include<iostream>
#include<set>
#include<time.h>
#include <stdlib.h>
using namespace std;
//线段切割法 无保底
//iTotalGold总金额 iNum份数 iBaseGold保底金额
void cutline(int iTotalGold, int iNum)
{
if (iNum > iTotalGold)
{
return;
}
if (iNum == iTotalGold)
{
for (int i = 0; i < iNum; ++i)
cout << 1 << " ";
cout << endl;
return;
}
std::set<int> setGold;
for (int i = 0; i < iNum-1; ++i)
{
while (1)
{
int iPos = rand() % iTotalGold;
if (setGold.find(iPos) == setGold.end())
{
setGold.insert(iPos);
break;
}
}
}
cout << "线段切割法(无保底):" << endl;
int iPreLine = 0;
for (auto &it : setGold)
{
cout << it - iPreLine << " ";
iPreLine = it;
}
cout << iTotalGold - iPreLine << " ";
cout << endl;
}
int main(void)
{
srand((unsigned int)time(0));//初始化种子为随机值
int iTotalGold = 100;
int iNum = 10;
int iBaseGold = 5;
cutline(iTotalGold, iNum);
return 0;
}发现缺点是由于过于随机导致有可能有小概率造成某个人分配过多，不过可以做一个保底就欧克啦！
双倍随机法
每次随机的时候，取0-每个人平均金额的2倍进行随机。
微信团队公布的算法好像就是这个。
例如：100个人分10分，每次随机都是0-100/10*2去随机，基本可以保证每个人平均在10左右，是相当平均的算法。不过需要注意最后几个人可能已经不足20的情况。
#include<iostream>
#include<vector>
#include<stdlib.h>
#include <iterator>
using namespace std;
//双倍随机法
//iTotalGold总金额 iNum份数 iBaseGold保底金额
void twobase(int iTotalGold, int iNum, int iBaseGold)
{
if (iNum *iBaseGold > iTotalGold)
{
cout << "保底太多 " << iBaseGold << endl;
return;
}
std::vector<int> veGold(iNum, iBaseGold);
iTotalGold -= iNum*iBaseGold;
int iBaseTmp = iTotalGold / iNum * 2;
for (int i = 0; i < iNum - 1; ++i)
{
if (iTotalGold == 0)
break;
int iTmp = 0;
if (iTotalGold >= iBaseTmp){
iTmp = rand()%iBaseTmp;
}
else
iTmp = rand() % iTotalGold;
veGold[i] += iTmp;
iTotalGold -= iTmp;
}
veGold[iNum - 1] = iTotalGold;
cout << "双倍随机法:" << endl;
copy(veGold.begin(), veGold.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
int main()
{
int iTotalGold = 100;
int iNum = 10;
int iBaseGold = 5;
twobase(iTotalGold, iNum, iBaseGold);
return 0;
}本文参考文章：
