前缀和+二分
由于安排的客人是单调递增的,考虑使用二分,由于每张卓子都有 $a_i$ 个位置,考虑用前缀和优化。
对于二分的写法,个人喜欢添加一个 $ans$ 用来记录答案。
注意开 $long$ $long$ 。
时间复杂度 $O(nlogn)$。
#include <bits/stdc++.h>
using namespace std;
const int N = 201001;
#define LL long long
LL a[N], s[N];
int n, m, ans;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], s[i] = s[i - 1] + a[i];
LL la = 0;
while (m--)
{
LL k;
cin >> k;
int l = 1, r = n, ans = n;
if (k + la >= s[n])
{
cout << n << "\n";
la = 0;
continue;
}
while (l <= r)
{
int mid = (l + r) >> 1;
if (s[mid] <= k + la)
l = mid + 1;
else
r = mid - 1, ans = mid;
}
if (k + la == s[ans])
cout << n - ans << "\n";
else
cout << n - ans + 1 << "\n";
la += k;
}
return 0;
}