Description

現(xiàn)在給你nn天的COVID-19COVID?19新增感染人數(shù)，有qq次詢問，每次詢問針對kk，問至少多少天患病人數(shù)會大于等于kk。

Input

第一行輸入兩個整數(shù)n(1n1e6)，q(1q1e6)
第二行有n個正整數(shù)ai表示第i天新增感染的人數(shù)(1a_i1e6)。
接下來q行，每行給出一個k(1k a_i)

Output

對于每個詢問，輸出一個整數(shù)m，代表至少m天患病人數(shù)會大于等于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.