题意
$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$不严密的想到：
- C在P的左边。因为C是左边密集右边稀疏，P是右边密集左边稀疏。
- 任意两个C或者任意两个P之间的间隔最大为1。因为如果两个P之间间隔为2，那么
CP??PP中间的两个?只能是C，且相互之间的间隔为1，小于了最左边C的那个2。
但是上面的结论其实有4种特殊情况：
- 最左边有一个P。形如
PCCPP。 - 最右边有一个C。形如
CCPPC。 - 最左边有一个P，最右边有一个C。形如
PCCPPC。 - 左边若干位全是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。
代码
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
}