今天早上0：00，SRM500……
注冊(cè)時(shí)，定睛一看，有個(gè)TC的Member陣亡了…你是否同意把這次比賽獎(jiǎng)金捐給他…本以為是11區(qū)人在海嘯中陣亡，沒想到是俄羅斯人，據(jù)傳聞?wù)f是勞累過度之類的……（大帝：你看看，你看看，又是聽說 =_=），諷刺的是這條新聞?wù)睦锩嫣字鳩B，然后墻了…………
不過獎(jiǎng)金啥的也只能YY了……
250是個(gè)很硬的題……前幾名里都有人徹底放棄了的……System掛掉了至少100人……
題意是這樣：給N個(gè)人（N<=500），需要投票選出一個(gè)，其中M（M<=min(50,N)）人有確定的想法，其他人投票只投給當(dāng)前票數(shù)最少的人，如果平票則在平票人中投第二輪，第三輪，原先如果有人確定想投某人，但是這人沒晉級(jí)下一輪，則之后他就成無想法了………這樣肯定有一些人被選出來的概率比較大，求最大的概率
Sample：
3
{1, 1, 1}
答案：1，1號(hào)一定被選出
5
{1, 2, 3}
答案：0，不可能選的完
（投完123后，人的得票數(shù)為01110，剩下兩個(gè)，一個(gè)投0一個(gè)投4，又從頭來了……）
20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
答案：0，第一輪：1234567，第二輪：剩下其中的6個(gè)，第三輪：剩下兩個(gè)，第四輪就選不出來了……
23
{17, 10, 3, 14, 22, 5, 11, 10, 22, 3, 14, 5, 11, 17}
答案：0.142857.....，第一輪剩下7個(gè)，第二輪剩下2個(gè)，第三輪能選出來1個(gè)，每個(gè)人被選出的概率都是一樣的……
這個(gè)問題不太好理解，多數(shù)人都卡在了讀題上……而且很容易沒有想法……
先寫了個(gè)模擬，然后逐漸摸清門道了……
當(dāng)時(shí)發(fā)現(xiàn)，前幾輪的走勢(shì)是必然的，后面的就有隨機(jī)性了
譬如
20
{1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0}
第一輪剩下的人，必然是1234567，但是后面，支持1234567的那14個(gè)人一定會(huì)給他們投票；其他6個(gè)沒想法的人就不一定投給誰了…
于是先模擬出來那些必然現(xiàn)象，然后，就是純粹和數(shù)字相關(guān)，和人無關(guān)的這么一件事情了……
大概就是N個(gè)人，M人候選這樣……由于N個(gè)人中，包含M＊X個(gè)有想法的人，會(huì)給這M人分別投M票，剩下N－M＊X個(gè)沒想法的人會(huì)給票少的人投，最后，下一輪的候選人就是N％M……一個(gè)小遞歸驗(yàn)證就行了……如果當(dāng)前M可以得到1，則有解，如果最后N％M ＝＝ 0，就是上面那種20個(gè)人給2個(gè)人投票那樣，投不出來……
事后看了別人的代碼想明白了，只需要模擬一步……
代碼：
1 class MafiaGame {
2 public double probabilityToLose(int N, int[] decisions) {
3 int[] cnt = new int[N];
4 int NoIdeaMan = N;
5 for (int i :decisions) {
6 cnt[i] ++;
7 NoIdeaMan --;
8 }
9 while (NoIdeaMan-->0) {
10 int min = 99999999;
11 for (int i : cnt) {
12 if (i < min) min = i;
13 }
14 for (int i = 0; i < N; i++) {
15 if (cnt[i] == min) {
16 cnt[i] ++;
17 break;
18 }
19 }
20 }
21 int Group = 0;
22 int max = 0;
23 for (int i : cnt) {
24 if (i > max) {
25 max = i;
26 Group = 0;
27 }
28 if (i == max) {
29 Group ++;
30 }
31 }
32 System.out.println(Group);
33 if (check(N,Group)) {
34 return 0.0;
35 }
36 return 1.0/Group;
37 }
38
39 boolean check(int N,int Group) {
40 if (Group == 1) return false;
41 if (N % Group == 0) return true;
42 return check(N,N%Group);
43 }
44 }
最后Systemtest階段，哥從400＋爬到了324……前面至少掛了100人……
rating -> 1591，再創(chuàng)歷史新高…………