先说结果，本次采用了概率论的离散分布以及分治法进行演算，从而得到一个随机区间比如[0,total]中[total/4,(total/4)+2] 的区间作为起始随机值的筛选区间是比较合适的
虽然让我用策略模式。。但因为真的没看出来为啥需要用这个模式。所以完全不想硬套.读题
思路演变 1.贪心[启发点:每个奖项至少被一个人选到,O(n2)] 试想一下，如果我们把<奖项n,奖项个数m>转化为<元素,权重>的关系。那么此时先随机选中m个人拿不同的元素，保证至少被一个人选到的贪心策略.再根据权重对每钟元素要进行m-1次离散。这样的效率是最低的。且不说发生随机碰撞的可能性大,关键是每种奖项随机区间会因为Random函数随机种子的问题(元素越小，出现的概率越大)。如果总人数足够小，甚至有可能出现连号的情况
2.位图法（二维数组）标记+每次调整迭代步长(随机区间)[启发点：尽可能让每个人选到，也就是分布均匀，但是随机初始区间还是要每次手动分配，循环次数太多，而且我们还要先对两两区间上限的最大公约数的倍数做一次标记处理O(n2)]
3.我们根据概率论+分治法。如下演算推断所示，将非一等奖的随机值控制在自己手里[启发点:如果我们一开始就知道哪个区间之后的迭代步长是有效的，那我们何不在第一次分配的时候就决定好的O(nlogn)]
可见时间，空间，随机值的离散分布有一个三角关系 要么选择 时间+离散分布 要么选择 空间+离散分布。因为每一次离散都要依赖上一次随机的值才能尽量减少随机碰撞。
question:
问题
幸运抽奖
关键词
可测试的代码，测试oracle，模拟技术
适用的设计模式
策略模式
描述
每年在Ringcentral的年度晚宴上都有幸运抽奖环节。设计一个程序来选择幸运的家伙！
需求
编写一个幸运抽奖程序，其输入是员工总数和奖金配置（一，二，...奖有多少个），并输出每个奖的获奖者列表
员工人数> =获奖人数
任何员工最多可获得1个奖项
您必须编写测试以证明您的代码正确，并且您的实现可以保证公平性
正确性：您的代码按预期工作
公平：每个员工都有相同的机会赢得相同的奖金（可以使用统计技术）
样品
输入：
员工总数：100（员工指数从0到99）
奖品配置：[1、2、3]（意味着我们将获得1名一等奖，2名二等奖和3名三等奖）
输出：
[[50]，[23、34]，[20、81、79]]（表示第50名员工获得一等奖，第23和第34名员工获得二等奖，依此类推）
提示
为了证明其正确性，您需要确保满足所有要求，例如任何员工最多只能获得一份奖金，等等。
为了证明公平，您可以多次使用相同的输入来运行程序，并检查是否关闭了每个员工相同奖品的获胜时间。
这是一个开放的问题，因此欢迎其他任何想法。
talk is cheap,show me your code
/*
* Copyright (c) 2001-2020 GuaHao.com Corporation Limited. All rights reserved.
* This software is the confidential and proprietary information of GuaHao Company.
* ("Confidential Information").
* You shall not disclose such Confidential Information and shall use it only
* in accordance with the terms of the license agreement you entered into with GuaHao.com.
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
/**
* @author chengxy
* 2020/3/25
*/
public class RandomAlogrim {
public static int getRandom(int min ,int max){
Random r = new Random();
return r.nextInt(max) % (max - min + 1) + min;
}
//比如3有三个人拿到 随机区间为9的倍数 9-18 18-27 27-36
//总奖品数，总人数
public static Map<Integer,List<Integer>> greedyPresent(int present,int total) {
int[] totals = new int[total];
//思路是这样。在经历了位图法+二维数组等一系列标记元素的情况
// 发现遗憾的是时间复杂度仍然是On2，而且还是没有自主的控制随机范围尽量均匀
//于是经过各种模拟演算，我终于发现 比如我们有100个人，此时设置1等奖1个 2等奖两个 3等奖3个
// 此时我们选择[25,27]这个区间中的随机数 25 26作为2等奖和3等奖的开始区间，按照他们分别的倍数进行随机步长的设置
//例如 2等奖 [25,50] [50,75] [75,100] 3等奖[26,52],[52,78] 这样便能保证足够公平。因为100的中位数是50
//那么此时就分成了两个区间，可是为什么要这样做呢？
// 通过概率论我们可以得出,如果我们从前半区间[1,25]开始迭代,
// 那么此时因为元素值比较小,所以累乘的步长也小,而前半区间的离散程度相对密集
//但如果是后半区间[50,100]的话，我们元素的步长太大，迭代很快就超过人员编号范围了
//所以我们此时必然选择前半区间[1,50],但是此时50显然也不合适，因为它的迭代步长太大了。而后结合概率论已经分治法做进一步分析
//前半区间[1,25]迭代速度过小，所以舍弃。故采用[25,27]区间，因为此区间的数只有三个元素，而且增长速度较快，
// 比较适合当起始的随机区间
int monitor = -1;//监视一等奖的变量
int[] presentLevel = {1, 2, 3};
Map<Integer,List<Integer>> receivePresent = new HashMap<>();
for (int i = 0; i <presentLevel.length; i++){
if (presentLevel[i] == 1){
int result = getRandom(1,total);
totals[result] = 1;//该元素已经被随机过
monitor = result;
List<Integer> receiveMan = new ArrayList<>();
receiveMan.add(result);
receivePresent.put(presentLevel[i],receiveMan);
}else {
//这里其实就是上面的总结,total/4就是分治切出来的开始区间,total-1就是除了一等奖之外的得奖个数
//此时我们暂时只考虑二、三等奖的情况(我是觉得从两次切分中位数的total/4开始,用户一般只会关注二等奖，三等奖是否公平
// 至于如果后面有五等奖六等奖的话那其实可以在[(total/4)-1,total/4])中先选出随机初始值，
// 步长增长速率缓慢，区间更多，这样也符合更多人中奖的原则
//此处设计复杂度为O(nlogn)
int wei = total/4;
int result = getRandom(total/4,wei+presentLevel.length-1);
for (int j=presentLevel[i];j>=0;j--){
//这里不取到两边，是因为伪随机数的特性，如果真的取到边界，由于各自向内收缩一位，所以我们可以选一个边界
int zhong = total/result;
int randomValue = getRandom(result+1,zhong*result-1);
System.out.println(randomValue);
//这里如果发生随机碰撞，或者取值到了收缩边界。亦或者是跟一等奖取到了同一位，
// 那么我们认为是偶然事件，取左边界result
if (totals[randomValue]==1 || randomValue == result+1 || randomValue == monitor){
List<Integer> receiveMan = new ArrayList<>();
receiveMan.add(result);
totals[result] = 1;
receivePresent.put(presentLevel[i],receiveMan);
}else{
List<Integer> receiveMan = new ArrayList<>();
receiveMan.add(randomValue);
totals[randomValue] = 1;
receivePresent.put(presentLevel[i],receiveMan);
}
}
}
}
////权重分别为 1 2 3
//for (int i = presentLevel.length - 1; i >= 0; i--) {
// if (i == 1){ //1等奖只有一个的话，就用随机出来的结果,如果有两个的话，2为权重，用1*2为随机范围跨度，取2的倍数 2-4 4-8
//
// int result = getRandom(1,total);
// totals[result] = 1;
// List<Integer> receiveMan = new ArrayList<>();
// receiveMan.add(result);
// receivePresent.put(presentLevel[i],receiveMan);
// }else {
//
// for (int j =i*i;j<total;j=j*i){
// //判断是否是奖品数组的最大公约数的倍数
// }
// }
//}
return receivePresent;
}
public static void main(String[] args){
Map<Integer,List<Integer>> a = greedyPresent(0,100);
//
//for(Map.Entry<Integer,List<Integer>> e:a.entrySet()){
//
// System.out.println("键是"+e.getKey());
//
// System.out.println("值是"+e.getValue().toString());
//
//}
}
}
