问一下代码在查询那里如何改用lower_bound省时间:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,q;
ll a[200005];
ll vis[200005];
ll res[200005]={1};
int main()
{
freopen("Guard.in","r",stdin);
freopen("Guard.out","w",stdout);
scanf("%lld%lld",&n,&q);
for(ll i=1;i<=n;i++)
{
scanf("%lld",a+i);
}
ll num=n;
ll cnt=0;
ll i=1,j=n;
while(i<j)
{
vis[cnt+1]=vis[cnt]+min(a[i],a[j]);
if(a[i]==a[j])
{
a[i]=0;
a[j]=0;
i++;
j--;
num-=2;
res[cnt+1]=num;
}
else if(a[i]>a[j])
{
a[i]-=a[j];
a[j]=0;
j--;
num--;
res[cnt+1]=num;
}
else if(a[i]<a[j])
{
a[j]-=a[i];
a[i]=0;
i++;
num--;
res[cnt+1]=num;
}
cnt++;
}
if(a[i]!=0)
{
vis[cnt+1]=vis[cnt]+a[i];
res[cnt+1]=1;
cnt++;
vis[cnt+1]=vis[cnt];
res[cnt+1]=0;
a[i]=0;
}
while(q--)
{
ll t;
ll flag=0;
scanf("%lld",&t);
for(ll i=1;i<=cnt;i++)
{
if(t<vis[i])
{
printf("%lld\n",res[i-1]);
flag=1;
break;
}
}
if(flag==0)
{
printf("Zombies ate your brain!\n");
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
Input 1
5 3
1 4 2 3 5
1
5
2
Output 1
4
2
4
Input 2
1 3
5
4
5
6
Output 2
1
Zombies ate your brain!
Zombies ate your brain!
Input 3
5 4
1 2 2 1 5
3
5
6
10
Output 3
3
1
Zombies ate your brain!
Zombies ate your brain!