5个海盗分100个金币，如何分配？

​ 5个海盗编号0-4， 要分配100枚金币。从编号为4开始，设计一个分配方案，如果能够使得超过半数的人同意分配方案，则按该方式分配，如果小于半数，则将此海盗丢入海中，3号依次进行。如果想要获得最多的金币，并且不被丢入海中，4号应该如何分配？

解题思路

​ 由于需要超过半数的人同意，即需要包括自己在内的3个人同意方案方可。而要使得其他海盗同意该方案，则需要使得海盗得到的金币要超过此方案之外的任一方案。

​ 我们依然从最简单的情形入手：

  • 1个海盗：全部分配给自己即可。
  • 2个海盗：海盗1无论如何分配，0均会投反对票，使得问题回退到情景一。
  • 3个海盗：只需给与海盗1一枚金币，海盗1就会同意该方案，否则1无法得到任何金币。所以分配方案为\(99, 1, 0\)
  • 4个海盗：依次类推

最优分配

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int pirateCoinAllocation(int n, int k) {
        /*
        n pirates split the k gold coin, from index 0 to index n-1, decide the allocation ,
        if over half of the pirates agree, then do it, else kill the one, and next. Get the
        max number of gold coin the index 0 can get and also survive.Note that one pirate 
        vote death unless it can make him get more coins.
         */

        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(k);
        int ret = 0;
        System.out.println(queue);
        for (int i = 2; i <= n; i++) {
            int needVoteCnt = i / 2;
            int curSum = 0;
            List<Integer> set = new ArrayList<>();
            if (needVoteCnt > queue.size()) {
                queue.offer(0);
                continue;
            }
            for (int j = 0; j < needVoteCnt; j++) {
                curSum += queue.peek() + 1;
                set.add(queue.poll());
            }
            if (curSum > k) {
                for (int c : set) {
                    queue.offer(c);
                }
                queue.offer(0);
            } else {
                queue.clear();
                for (int j = 0; j < i - 1 - needVoteCnt; j++) {
                    queue.offer(0);
                }
                for (int c : set) {
                    queue.offer(c + 1);
                }
                queue.offer(k - curSum);
                ret = k - curSum;
            }
            System.out.printf("cur number of pirates: %d, allocation: %s\n", i, queue);
        }
        return ret;
    }