题目链接在这里：Problem - H - Codeforces

我们首先来看如果正着做的话，需要有一些高位的数降到0来补充，但是我们不知道哪几个高位的数需要降，如果每降一个高位来重新计算一下结果的话很显然是会超时的。我们可以发现，如果当前位的数要降的话，比它高的位也是要降的。这样我们可以二分这个要降的位，争取把每次查询的时间复杂度化简到O(N)的级别。

很显然我们能观察到这里哪一个数降不降和答案其实是等价的。

然后我们去考虑检验结果的问题。如果正着做的话我们会遇到一些困难，所以考虑倒着去做，由结果推到给定状态，也就是从结果位一个一个推到第一位，只要能推出是初始状态的子集就行了。如果当前位减一的话，相当于前面的每一位都要加一，这对前面的每一位都是等价的，所以说我们可以用一个变量去维护，然后往回推。可以发现，如果对于初始状态来说当前位一直是0的话，个数是以指数形式增长的，所以我们需要增加一个判断条件，如果当前位的个数超过了总共初始状态的1的个数就跳。

这里如果一个数>x 它就变成0；如果一个数小于x 它就会让比它小的每一个数都至少加1。

如果推到0以后多的位能补回到之前缺的位上，那么就是可行的，如果0多了，说明达到当前结果需要更多比当前结果大的数来变为0，所以是不可行的。

参考代码：

 

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=100105;
 5 LL n,a[MAX],b[MAX],mx;
 6 bool feasible(LL x){
 7     LL i,j;
 8     LL now,le,xx,yy;
 9     now=1,le=b[x];
10     for (i=x-1;i>=1;i--){
11         if (now>b[0]) return false;
12         if (now==a[i]) continue;
13         if (now<a[i]){
14             le+=a[i]-now;
15             continue;
16         }
17         if (now>a[i]){
18             now=now+(now-a[i]);
19             continue;
20         }
21     }
22     if (now-a[0]<=le) return true;
23     else return false;
24 }
25 int main(){
26 //    freopen ("h.in","r",stdin);
27 //    freopen ("h.out","w",stdout);
28     LL i,j;
29     LL low,high,mid,ans;
30     scanf("%lld",&n);
31     memset(a,0,sizeof(a));
32     for (i=0;i<n;i++) scanf("%lld",a+i);
33     b[n+1]=0;
34     for (i=n-1;i>=0;i--)
35         b[i]=a[i]+b[i+1];
36     if (b[0]==1){
37         if (a[0]==1 || a[1]==1) printf("1");
38         else{
39             i=2;
40             while (a[i]==0) i++;
41             printf("%lld",i);
42         }
43         return 0;
44     }
45     
46     low=1;high=100100ll;
47     while (low<=high){
48         mid=(low+high)>>1;
49         if (feasible(mid)){
50             ans=mid;
51             low=mid+1;
52         }
53         else high=mid-1;
54     }
55     printf("%lld",ans);
56     return 0;
57 }