「Jack 的钻石」题解

发表于 分类于 阅读次数： Waline：
看似迷惑的题目，其实也有巧妙的解法！

题意

题目

有 \(n\) 名黑帮成员，为了方便，分别编号为 \(1\) 到 \(n\)。并且假设老大编号为 \(n\)。开始，Jack 老大应把战利品拿出来给大家过目，并提出一个分配方案，然后所有 \(n\) 名成员（含自己）分别表示赞同或不赞同，如果不赞同的成员比例严格大于一半，那么根据规矩，老大 Jack 就会被处理掉，由编号为 \(n-1\) 的成员维任，并依照同样的过程继续分配刚才的战利品，否则这个分配过程就完成了。在黑帮团伙中成员们的目的都比较单纯，所有成员首先要保住自己的性命，在能保住性命的前提下，当然要拿尽可能多的钻石: 一旦在当前这个方案里，他拿到的钻石数不大于之后所有情况下可能拿到的最大钻石数，那么他就会反对当前分配方案，否则支持。

这个黑帮是一一个理性的黑帮（不然早就被端掉了），因此你可以认为所有成员都是无穷阶理性的，也就是说每个人都知道其他人也拥有与自己相同的想法，在任意步过后也同样追求最优解，并且计算上不会出错。

Jack 老大在尝试制定不同的分配原则，因此有时他要求自己必须要分配到至少 \(1\) 个，而有时不需要，现在他想知道为了满足分配规则和保住他的性命，钻石至少要有多少个。

思路

记最小需要的钻石为 \(D\)。
分别对 \(S = 0\) 和 \(S = 1\) 进行讨论。

对于 S = 1

首先对于 \(n = 1\) 和 \(n = 2\) ，\(D = 1\)，即给 Jack 自己。

然后对于 \(n = 3\) 时，因为就算 Jack 被杀，\(2\) 号也可以存活，所以 \(1\) 号和 \(2\) 号都反对。所以 Jack 必须拿出一个钻石给 \(1\) 号（因为 \(2\) 号在 Jack 被杀后也可以拿到 \(1\) 个钻石）

以此类推，\(n = 4\) 时需要给 \(2\) 号和 \(4\) 号。

综上，\(n\) 个人时需要给所有的 \(x (x \equiv n \pmod 2)\)，即给所有编号与 \(n\) 奇偶性相同的人。所以答案为 \(\lceil \frac n2 \rceil\)。

对于 S = 0

首先对于 \(n = 1\) 和 \(n = 2\)，\(D = 0\)。

然后我们考虑什么情况下 \(D = 0\)。

  • 在 \(n = 3\) 时 \(D = 0\) 是不行的，因为此时只有 Jack 一个人投票。
  • 在 \(n = 4\) 时，\(3\) 号会投票，因为当 Jack 死后就会变成 \(n = 3\) 的情况，而此时上面算过 \(3\) 号必死。此时 \(D = 0\) 时 Jack 可以活下来。
  • 在 \(n = 5\) 时，只有 Jack 会投票。
  • 在 \(n = 6\) 时，\(5, 6\) 号会投票。
  • 在 \(n = 7\) 时，\(5,6,7\) 号会投票，因为 \(6,7\) 号都死后 \(5\) 还是必死。
  • 在 \(n = 8\) 时，\(5,6,7,8\) 号会投票，Jack 存活。

所以，\(i\) 号会投票当且仅当 \(i = n\) 或 人数在 \(i\) 和 \(n\) 之间时提出方案的人都必死。

根据这个，容易得出当 \(n = 2^k\) 时 Jack 可以存活。

那么，对于不是 \(2\) 的正整数次幂的 \(n\)，就只有用钻石让 Jack 活下来。

对于 \(n = 2^k + 2m (k, m \in \mathbb Z^+)\)，\(2^k\) 部分不需要任何钻石，而 \(2m\) 部分每两个人需要一个钻石让其中一个人投票，所以 \(D = m\)。

现在的任务就是找最小的 \(m\) 使得 \(n = 2^k + 2m\)。

当 \(n\) 为偶数时，\(m_{min} = \frac{n - highbit(n)}{2}\)。其中 \(highbit(x)\) 表示 \(x\) 最高的二进制位的位权（即最大的 \(2^k\)）

当 \(n\) 为奇数时，因为 \(2m\) 是偶数，所以只有让 \(2^k\) 为奇数，那么 \(k = 0\)，所以 \(m = \frac{n - 1}{2}\)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>

int highbit(int x) {
	for(int i = 31; i >= 0; i--) if(x >> i & 1) return 1 << i;
	return 0;
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		int n, t;
		scanf("%d%d", &n, &t);
		if(t == 1) printf("%d\n", (n + 1) / 2); // A1
		else printf("%d\n", (n & 1) ? (n - 1) / 2 : (n - highbit(n)) / 2); // A2
	}
	return 0;
}