Codeforces Round #718 Group Photo - 二分

题意

$n$个人拍照，要把这些人分成两部分，一部分人拿C的牌子，一部分人拿P的牌子。现在要求拿C的人的下标满足$c_i-c_{i-1}\leq c_{i+1}-c_i$，拿P的人的下标满足$p_i-p_{i-1}\geq p_{i+1}-p_i$，且$\sum\limits_{x\in C} a_x < \sum\limits_{y\in P} a_y.$。问总共有多少分法。

题解

首先我们根据$c_i-c_{i-1}\leq c_{i+1}-c_i$和$p_i-p_{i-1}\geq p_{i+1}-p_i$不严密的想到：

1. C在P的左边。因为C是左边密集右边稀疏，P是右边密集左边稀疏。
2. 任意两个C或者任意两个P之间的间隔最大为1。因为如果两个P之间间隔为2，那么CP??PP中间的两个?只能是C，且相互之间的间隔为1，小于了最左边C的那个2。

但是上面的结论其实有4种特殊情况：

1. 最左边有一个P。形如PCCPP。
2. 最右边有一个C。形如CCPPC。
3. 最左边有一个P，最右边有一个C。形如PCCPPC。
4. 左边若干位全是P，剩下右边全是C。形如PPPPCCC。
   其中前三个特殊情况都只能有一位是特殊的。不难发现，如果多加一位会产生形如PPCCPP这种不满足条件的结果。

排除第4种特殊情况，普通情况+3种特殊情况我们可以表示为：(P)?(C){1,}(PC)*(P){1,}(C)?。也就是开头P可选，结尾C可选。然后两侧至少一位C和P，剩余位置填充PC。

于是我们可以注意到对于已经选定长度的C，PC越多，P的和越小。

于是我们根据4种情况，枚举C的长度。之后再通过二分找到PC的最大长度，就可以得到当前情况下指定C的长度后的可能数目。
以第2种特殊情况下，C的长度为3举例，即：CCC???????C
存在以下可能CCC|PCPCPC|P|C，CCC|PCPC|PPP|C，CCC|PC|PPPPP|C，CCC|PPPPPPP|C。
显然PC越少P越多。所以我们可以通过二分得到做多能有多少个PC。

代码

实现思路

建议抽一个函数，以便在外部情况给定的条件下，专门二分PC的数目

    private static long solve(int last_c_pos, int last_unknown_pos, long current_sum_P_minus_C) {
        int len = last_unknown_pos - last_c_pos - 1;
        if (len % 2 == 1) len--;
        int left = 0;
        int right = len / 2;
        while (left < right) {
            // binary search
        }
        // return the number of all possibilities
    }