红包算法
发布于
题目
给定一个红包总金额和分红包的人数,输出每个人随机抢到的红包数量。
要求:
-
每个人都要抢到红包,并且金额随机。
-
每个人抢到的金额数不小于1
-
每个人抢到的金额数不超过总金额的30%
例如总金额100,人数10,输出【19 20 15 1 25 14 2 2 1 1】
思路
- 首先是这个人数必须要大于等于4,否则直接都不满足第三个条件
- new 一个数组,让这个数据的每个数据都等于1
- new一个随机数在1到30之间
代码
public static void main(String[] args) {
int total=0;
int count=50000;
for (int i = 0; i < count; i++) {
int packet = getPacket(100, 10);
total=total+packet;
}
//这个是来测试这段代码的性能,基本上在count=50的时候,已经稳定在了15了,时间复杂度基本上可以说是1.5N,N就是人员的数量
System.out.println(total/count);
// for (int i : packet) {
// System.out.print(i+",");
// }
}
public static int getPacket(int money,int number){
if(number < 4 || money < number){
throw new IllegalArgumentException("illegal argument");
}
int[] result = new int[number];
for (int i = 0; i < number; i++) {
result[i] = 1;
}
double threshold = money * 0.3;
int remain = money - number;
int index = 0;
Random random = new Random();
int count=0;
while (remain > 0){
int i = random.nextInt(remain);
if(i == 0){
i = 1;
}
double now = result[index] + i;
if(now <= threshold){
result[index] = (int)now;
remain -= i;
}
index ++;
count++;
if(index == number){
index = 0;
}
}
//System.out.println(count);
return count;
}
收获
- 在所有数据都有一个最小值的数据的情况下,可以假设所有的值都是最小值,在此基础至上,来进行数据处理
- random.nextInt(x)的方法,返回(0,x],即大于0小于等于x