「Jack 的钻石」题解

题意

题目

有 $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(\mathrm{mod}2))$，即给所有编号与 $n$ 奇偶性相同的人。所以答案为 $\lceil \frac{n}{2}\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}$。

代码

#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;
}