Question

pascal程序(序列)

问题描述
有一个非递减的整数序列S1，S2，S3，……，Sn+1（Si<=Si+1）。定义序列m1，m2，…，mn­为S的“M序列”，其中mi=(Si+Si+1)/2。
例如，S=(1, 3, 3, 5)，则m=(2, 3, 4)。
现在给你序列m，要你求有多少个S序列的“M序列”是序列m。
输入(sequence.in)
第一行一个整数n，
下接n行，每行一个整数mi
输出(sequence.out)
一个整数，表示有多少个S序列的“M序列”是序列m
样例

sequence.in
3
2
5
9
sequence.out
4

样例说明：存在如下四个数列S满足要求：
2，2，8，10；
1，3，7，11；
0，4，6，12；
-1，5，5，13。
数据范围
50%的数据n<=1000，mi<=20000
100%的数据2<=n<=100000，mi<=109.

给我解题的思路就行

Answer 1

先检查序列m吧，mi<=m(i+1)，否则就是0了
然后，只要确定S1就可以确定整个数列
那就先找一个符合要求的S序列，注意，S1<=m1/2，这样就从某个很小的数（-10^9一定够了，再大点可不可以再研究）到m1/2（或m1/2-1/2)，使用二分查找找一个成立的S1。
至于直接s1=m1/2(或m1/2-1/2)是否成立，说不准，貌似不成立。
总之，先找到一个成立的S序列。
（以下k为正整数）
然后，用调整的思路考虑。
（1）如果S1加一，那么S2减一，S3加一，S4减一，S5加一.......
那么S(k*2-1)就与S（k*2）越来越接近，当它们相差一或者相等时就不可继续调整，那最小的S（k*2）-S(k*2-1)再div 2就是S1加一的次数限制。
这个次数限制设为a1
（2）如果S1减一，那么.......
这次是S（k*2)与S（k*2+1）决定次数限制，思路一样，得到a2
好，现在，有一个可行的S序列，S1增加有a1种，S1减少有a2种。
那总数就是，a1+1+a2