Description
你是一只僵尸。
你现在和 \(n - 1\) 个僵尸站在一起分配大脑。你的编号是 \(1\)，其他僵尸编号 \(2 \sim n\)。
僵尸们按照编号从小到大的顺序提出分配方案（一个方案是指每个僵尸分配几个大脑，大脑不能有剩余），然后所有僵尸进行投票，如果得票数大于等于一半方案就通过，否则当前的僵尸会被其它僵尸吃掉，由下一个僵尸进行分配。
僵尸们都很贪婪和残忍，但它们更不想被吃掉，所以僵尸们会在保证自己不被吃掉的情况下提出自己获得的大脑最多的方案，并且当且仅当吃掉分配的僵尸严格劣于同意分配方案时才会投赞同票。
给定 \(n\)，现在你想活下去，并且获得至少 \(m\) 个大脑，请问至少需要多少大脑才能满足？
数据范围 : \(n \leqslant 10^{9}, m \in \{0, 1\}.\)
Tutorial
首先考虑 \(m = 1\) 的情况。
容易知道，当 \(n = 1\) 或 \(n = 2\) 时，不需要其它任何人同意，所以只需要给自己分配一个脑子即可，答案为 \(1\)。
当 \(n = 3\) 时，\(1\) 号不可能获得 \(2\) 号的投票，因为 \(1\) 号死后 \(2\) 号可以独占所有脑子，于是 \(1\) 号只能去争取 \(3\) 号的同意。又因为如果让 \(2\) 号来分配，\(3\) 号一个脑子都得不到，所以分给它 \(1\) 个脑子即可获得它的同意，答案为 \(2\)。
考虑不断将 \(n\) 增加来考虑，可以发现，在上一步中可以获得脑子的僵尸是无法收买的，于是给上一步中无法获得脑子的僵尸分别分配 \(1\) 个脑子就可以获得它们的同意。
综上，当 \(m = 1\) 时，答案为 \(\left\lfloor\frac{n + 1}{2}\right\rfloor\)。
然后考虑 \(m = 0\) 的情况。
首先可以确定一个答案的上界，即考虑到 \(m = 1\) 情况下的分法，答案至多为 \(\left\lfloor\frac{n - 1}{2}\right\rfloor\)。
考虑当答案为 \(0\) 时有哪些僵尸可以存活:
首先给僵尸重新标号，记最后提方案的僵尸为 \(1\) 号，倒数第二个为 \(2\) 号，依此类推。
容易知道，当 \(n = 1\) 或 \(n = 2\) 时，所有僵尸均可存活。
\(3\) 号僵尸无法牵扯任何僵尸的利益，所以它无法存活。
\(4\) 号僵尸死后，\(3\) 号僵尸也会死，于是它获得 \(3\) 号僵尸的支持，可以存活。
\(5, 6, 7\) 号僵尸全部死后 \(1, 2, 3, 4\) 号僵尸也不会有任何损失，于是它们都不会同意 \(5, 6, 7\) 号僵尸的方案，所以 \(5, 6, 7\) 号无法存活。
\(8\) 号僵尸死后 \(5, 6, 7\) 号会死，于是它可以获得除自己外 \(3\) 只僵尸的支持，可以存活。
到这里，我们可以找到规律，在用到 \(0\) 个脑子的情况下，\(1, 2, 4, 8, 16, \cdots\) 号僵尸可以存活。
用与之前类似的方式分析脑子总数为 \(1, 2, 3, \cdots\) 的情况，我们可以发现，当脑子总数为 \(B\) 时，存活僵尸的集合为 \(\{1, 2, \cdots, 2B\} \cup \{2B + 2^{i}|i \in N^{\ast}\}\)。
当 \(n \equiv 1 \pmod 2\) 时，\(n\) 仅有可能在集合 \(\{1, 2, \cdots, 2(B + 1)\}\) 中出现，于是答案为 \(\frac{n - 1}{2}\)。
当 \(n \equiv 0 \pmod 2\) 时，可以找到最大的 \(2\) 的幂 \(p\) 满足 \(p \leqslant n\)，此时 \(n\) 会在 \(B = \frac{n - p}{2}\) 时第一次出现在集合中，于是答案即为 \(\frac{n - p}{2}\)。
综上，时间复杂度 \(\Theta(\log n)\)。
Reference Code
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main () {
cin >> n, m = 1/*0*/;
if (m == 1) printf("%d\n", (n + 1) / 2);
else if (n & 1) printf("%d\n", (n - 1) / 2);
else {
int p = 1;
while (p * 2 <= n) p *= 2;
printf("%d\n", (n - p) / 2);
}
return 0;
}
