感染(mid)

Description

现在给你nn天的COVID-19COVID−19新增感染人数，有qq次询问，每次询问针对kk，问至少多少天患病人数会大于等于kk。

Input

第一行输入两个整数n(1 $\leq$ n $\leq$ 1e6)，q(1 $\leq$ q $\leq$ 1e6)
第二行有n个正整数ai表示第i天新增感染的人数(1 $\leq$ a_i $\leq$ 1e6)。
接下来q行，每行给出一个k(1 $\leq$ k $\leq$ $\sum_{i=1}^{n}$ a_i)

Output

对于每个询问，输出一个整数m，代表至少m天患病人数会大于等于k

Sample Input 1

3 2
1 2 3
1
5

Sample Output 1

1
3

Source

nuoyanli.com

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
ll a[maxn];
ll sum[maxn];
ll n, q;
int main()
{
    scanf("%lld%lld",&n,&q);
    memset(sum, 0, sizeof(sum));
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    ll m;
    while(q--)
    {
        scanf("%lld",&m);
        printf("%d\n",lower_bound(sum, sum + n, m) - sum);
    }
    return 0;
}

Analysis:

First use the Prefix Sum prossing.Then consider dichotomy,because if use Brute-Force, it will TLE.

detail:

1.Prefix Sum.Working with arrays:

sum[i] = sum[i-1] + a[i];

2.lower_bound(). Dichotomy.