大哈爬楼梯
题目ID：8593
题目描述
大哈有天梦到自己在爬楼梯，一共有n级台阶。然后突发奇想，要是自己的腿长可以变的话其实爬到的高度也不同。比如2,3岁的小孩子，因为腿太短了，所以一级台阶都上不去；如果他有姚明那么长的腿，那可能即便这个台阶高一米，也能跨上去。给出A数组，代表第i级台阶和前一级台阶的高度差。比如
A
1
3
,
A
2
1
A
1
=3,A
2
=1，那此时第2级台阶的高度就是3 + 1 = 4。然后大哈问q次，每次问如果他一步能跨Bi米的高度，那么最高能爬多高？
输入格式
第一行两个整数n,q，分别代表台阶数和询问的数量
第二行n个整数Ai ，代表第i级台阶和前一级的高度差，第1级台阶前就是地面，高度为0。
第三行q个整数Bi ，代表每次的询问
输出格式
一行，对于每次询问回答最高能爬多高。
问题代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[200005],b[200005],sum[200005];
bool check2(int x,int y)
{
int last=0;
for(int i=1;i<=x;i++)
{
if(sum[i]-sum[last]<=y)
{
last=i;
}
}
if(last==x)
{
return true;
}
else
{
return false;
}
}
signed check(int x)
{
int l=0;
int r=n;
while(l<r)
{
int mid=(l+r+1)/2;
if(check2(mid,x))
{
l=mid;
}
else
{
r=mid-1;
}
}
return l;
}
signed main(void)
{
cin.sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=q;i++)
{
cin>>b[i];
}
for(int i=1;i<=q;i++)
{
int k=check(b[i]);
cout<<sum[k]<<" ";
}
return 0;
}
