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|CCCC|PCPC|PPP|CCCC|PC|PPPPP|CCCC|PPPPPPP|C
显然PC越少P越多。所以我们可以通过二分得到做多能有多少个PC

代码

Submission #114072656 - Codeforces
Codeforces. Programming competitions and contests, programming community

实现思路

建议抽一个函数,以便在外部情况给定的条件下,专门二分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
    }