AcWing 5385. 餐厅
原题链接
中等
作者:
Liana
,
2024-01-14 00:42:20
,
所有人可见
,
阅读 48
//前缀和+二分
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//c++在1s内大概10的7-8次方运算,样例200000只有时间复杂度在nlogn下才能1s内完成
//由nlogn想到二分
typedef long long LL; //重命名 10的14次方要用ll
const int N=200010; //定义数组用常量
int n,q;
LL s[N];
int work(LL sum){ //二分
int l=0,r=n;
while(l<r){
int mid=l+r+1 >>1; //要+1
if(s[mid]<=sum) l=mid;
else r=mid-1;
}
return n-r; //返回剩余桌
}
int main()
{
cin >>n >>q;
for(int i=1;i<=n;i++){
LL x;
scanf("%lld", &x);
s[i]=s[i-1]+x; //前缀和,前面桌所有的座位和
}
LL sum=0;
while(q--){
LL x;
scanf("%lld",&x); //新一波人数
sum+=x; //现场总共人数
if(sum>=s[n]) sum=0; //桌满清人
printf("%d\n",work(sum)); //二分找少一桌不够,多一桌有剩的临界桌号
}
return 0;
}