AcWing 5385. 餐厅
原题链接
中等
作者:
jayket
,
2024-01-14 10:30:33
,
所有人可见
,
阅读 54
感觉这样的二分会常见一点
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define int long long
const int N=2*1e5+1;
int a[N];
int sum=0;
signed main(void){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,q;cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>a[i];a[i]+=a[i-1];
}
for(int i=1;i<=q;++i){
int x;cin>>x;
sum+=x;
if(sum>=a[n])sum=0;
int ans=n;
int l=0,r=n-1;
while(l<=r){
int mid=l+r>>1;
if(a[mid]<=sum){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<n-ans<<"\n";
}
return 0;
}