倍增思想
题目:给定一个长度为N的序列a,进行若干次询问,对于每次给定的一个整数T,求出最大的k,使得序列的前k项和小于T.算法必须是在线的.假设a[i] >= 0

//倍增和二分都是在一定的范围寻找答案的手段,根据实际问题选择这两种手段
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], s[N];
int main()
{
    int N;
    cin >> N;
    for(int i = 1; i <= N; i ++ )
    {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    int T;
    while(cin >> T)
    {
        int sum = 0, k = 0, p = 1;  //sum表示计算的结果,k表示区间的左端点,p表示区间的长度
        while(p)
        {
            if(k + p <= N && sum + s[k + p] - s[k] <= T)
                sum += s[k + p] - s[k], k += p, p *= 2;
            else
                p /= 2;
        }

        cout << k << '\n';
    }
}