请教一个算法题：摇骰子， 3 个 1 和两个五一个六比， 3 个 1 获胜这种

[NicholasZhan]

楼主今天去面试了，最后的压轴题是： A 和 B 两人摇骰子，一人摇 5 次。要我找出他们俩谁赢了。获胜规则是这样的：相同数字出现最多的获胜，次数相同则数字大的获胜。例如：A 出了 6 个 1，B 出了 5 个 6 和 1 个 5，则 A 获胜。楼主的思路是先统计每人每个数字出现次数，然后按照出现次数和数字本身降序排列。排序规则是这样的，出现次数多的大，次数相同则比较数字。这样就能比较出胜负了。

没想到的是，面试官突然把题目升级了：假设有 5000 个人，每个骰子有 5000 个面，每个人摇 5000 次，还是一样的规则，让我找出获胜者😢。原来的算法肯定是不行的，面试官给的提示是如何遍历一遍就给每个人打个分，然后比较分数，我只想到了权重，出现次数越多权重越大。但是具体的算法还是没能设计出来，听闻 V 站大佬多，特来请教下 ORZ 。

[cpstar]

8 进制比特位，不知道行不行，LZ 试试

[wy315700]

5000 进制

[cpstar]

5000 个面啊。。。删除我 1 楼的话

[xloger]

上班摸鱼中，没仔细看题啊，“遍历一遍就给每个人打个分”，如你所说权重，那意思是比如没重复的就是正常分数，重复一次的就是正常分数*5000，重复两次就是正常分数*5000*2 的这个思路？计算一个数，这个数是重复 N 的最小值能大于重复 N-1 的最大值的，把这个设为权重，那重复次数多分数一定高于次数低的。
好，我继续去工作了...大佬们加油！

[cpstar]

但是从取最大的算法看，确实只遍历一次足以。只不过每次遍历，需要比较的东西太多。
反正不是排序算法，不用考虑如何把 O(n^2)降到 O(nlogn)之类的

[binux]

就是取最大，最多就是自定义一个比较算法罢了。

[shpkng]

存个当前最佳结果(点数和次数)和当前最高玩家的 id,
for 5000 遍历所有玩家,
每次循环里模拟投骰子,
循环完和当前最大值比,

这样就是一次循环, 你的解法里存每个人的数据再去排序是没意义的, 直接留最大的那个就好了, 因为题目的要求只是得到一个胜者

[bfdh]

66654 和 66611 谁胜？
前者胜的话，确实遍历一次就行；后者胜的话，我再想想。

[NicholasZhan]

@bfdh 后者胜

[NicholasZhan]

规则有点像我们斗地主中的炸弹，相同的牌越多，威力越大。大的抵消了，再看第二大的炸弹，以此类推

[misdake]

先按照第一段那样统计每个人的结果，得到有序的(次数,数字)列表，把这个列表看作字符串，这个字符串就是得分，或者把他编码成一个 5000 进制的数字，每一位依次是(次数 1, 数字 1, 次数 2, 数字 2, ..., 次数 n, 数字 n, ...)。后面没有了就填 0 。
然后写一个“字符串”比较或者这个 5000 进制数字比较的函数，然后根据需求进行排序或者取最大。

[cpstar]

sum[5000][5000]=0//全都清零，第一维为人，第二维为骰子结果
maxp=0//最大的人
maxr=0//最大的骰子结果
maxs=0//最大的骰子技术
for (ppl=1..5000) {//遍历人
for (times=1..5000) {//遍历次数
sum[ppl][result]++//result 为当此骰子结果
if(sum[ppl][result]>maxs||(sum[ppl][result]=maxs&&result>maxr)) {//次数超，或者次数相等结果超
maxp=ppl;maxr=result;maxs=sum[ppl][result];
}
}
}

[cpstar]

@cpstar 12# 的方法解决不了 8#。
8#的问题已经涉及排序了。

[tyx1703]

同 2 楼，n 进制解决

6 面骰子的权重：6^0 * S_1 + 6^1 * S_2 + … + 6^5 * S_6，其中 S_n 为 出现 n 次的点数的和

66654: (6+6+6) * 6^5 + (5+4) * 6^0
66611: (6+6+6) * 6^5 + (1+1) * 6^1

[zmxnv123]

如果 A > B & B > C => A > C，我理解取最大肯定是一个 O(n)算法

[NicholasZhan]

@tyx1703 老哥你有考虑过幂运算的溢出问题吗😂

[cpstar]

@tyx1703 14# @NicholasZhan 16# 溢出还不算事，两个 6 四个 5 要赢于三个 6 三个 5 的。

另外 14#的算法写错了吧，没看懂
66654 不应该是 6*3*6^5+5*6^4+4*6^3 么
66611 不应该是 6*3*6^5+1*2*6^0 么？

如果是这样的话，
A:665555: 6*2*6^5+5*4*6^4=119232
B:666555: 6*3*6^5+5*3*6^4=159408
这就错了，

[lin07hui]

权重：5000 * (数量 - 1) * 骰子值 + 骰子值

[lin07hui]

@lin07hui 18# 权重：5000 * (数量 - 1) + 骰子值

[tyx1703]

@NicholasZhan 这只是举个计算的例子，高进制所有位的值保存在数组中，按位比较

@cpstar 写错了，应该是 (6+6+6) * 6^2 + (1+1) * 6^1

665555: 6 出现 2 次，放在第 2 位； 5 出现 4 次，放在第 4 位
5*4*6^3 + 6*2*6^1

666555: 6 出现 3 次，放在第 3 位； 5 出现 3 次，放在第 3 位
(6*3 + 5*3) * 6^2