Description
现在给你nn天的COVID-19COVID−19新增感染人数，有qq次询问，每次询问针对kk，问至少多少天患病人数会大于等于kk。
Input
第一行输入两个整数n(1n
1e6)，q(1
q
1e6)
第二行有n个正整数ai表示第i天新增感染的人数(1ai
1e6)。
接下来q行，每行给出一个k(1k
ai)
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.
