倍增算法的思想

 1 #include
 2 using namespace std;
 3 const int N=1e5+5;
 4 int A[N],s[N];
 5 int main()
 6 {
 7     int n,m;
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++)
10     {
11         cin>>A[i];
12         s[i]=s[i-1]+A[i];
13     }
14     //数组s k后面的p个数 
15     while(m--)
16     {
17         int p=1,k=0,sum=0;
18         while(p)
19         {
20             int T;
21             cin>>T;
22             if(sum+s[k+p]-s[k]<=T)
23             {
24                 sum+=s[k+p]-s[k];
25                 k+=p;p<<=1;
26             }
27             else p>>=1;
28         }
29         cout<endl;
30     }
31     return 0;
32 }