前缀和的最大k

问题

给定一个长度为 n 的数列A，然后进行若干次询问，每次给定一个整数 T ，求出最大的 k ，满足$\sum_{i=1}^k A[i] \le T$。

要求算法必须要是在线的（几必须及时回答每次询问的问题，不能等待接收到所有的询问之后再做统一处理）。

输入格式

第一行输入一个整数 n ，代表数组A的长度，接下来的第 n 行输入一个整数，代表A[1]-A[n]，之后输入一个整数m，表示询问的次数，接下来m行代表每个询问。

输出格式

输出 m 行整数，每行代表一个询问的答案。

数据范围、

$0\le T \le \sum_{i=1}^k A[i]$

$0\le A[i] \le 100000$

$1\le n \le 100000$

$1\le m \le 10000$

输入样例

10
2 
3 
8 
15 
30 
5 
1 
2 
10 
1
2
10
30

输出样例

2
4

思路

思路一

二分，直接计算出数组A的前缀和数组S，再二分k的值，即可得到答案。

思路二

倍增，同上，先计算出前缀和，再按如下进行计算：

1. 令 p = 1, k = 0, sum = 0
2. 比较“A数组中 k 之后的 p 个数的和”与 T 的关系，也就是说，如果 sum + S[k+p]-S[k] <= T，则令 sum += S[k+p] - S[k]，k += p， p *= 2。即为累加上这 p 个数的和，然后把p的跨度增长一倍。如果 sum + S[k+p]-S[k] > T，则令 p /= 2,。
3. 重复上一步，直到 p 的值为 0 ，此时即为答案。

题解

题解一

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 1e5 + 5;
int n;
int a[MAX];
long long s[MAX];

int find_k(int t) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (s[mid] <= t) l = mid;
        else r = mid - 1;
    }

    return l;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i + 1]);
        s[i + 1] = s[i] + a[i + 1];
    }

    int m, t;
    cin >> m;
    for (int j = 0; j < m; ++j) {
        scanf("%d", &t);
        cout << find_k(t) << endl;
    }

    return 0;
}

题解二

#include<iostream>
#include<cstdio>

using namespace std;

const int MAX = 1e5 + 5;
int n;
int a[MAX];
long long s[MAX];

int find_k(long long t) {
    int k = 0, p = 1;
    long long sum = 0;
    while (p) {
        long long tmp = s[k + p] - s[k];
        if (tmp + sum <= t) {
            sum += tmp;
            k += p;
            p *= 2;
        } else p /= 2;
    }

    return k;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i + 1]);
        s[i + 1] = s[i] + a[i + 1];
    }

    int m;
    long long t;
    cin >> m;
    for (int j = 0; j < m; ++j) {
        scanf("%d", &t);
        cout << find_k(t) << endl;
    }

    return 0;
}