做法一
预处理座位数数组 $a[i]$ 的前缀和 $s[i]$,维护被使用的最后一张桌子 $id$ 和它的空闲座位数 $cnt$,则总空闲座位数等于 $sum[n] - sum[id] + cnt$。新一波客人到来时,从 $id$ 开始往后逐张桌子安排他们落座,由于编号和找到的空闲座位数具有单调性,因此可二分出能容纳 $k$ 个客人的最小结尾桌号,用它更新 $id$ 和 $cnt$,则没有被坐满的桌子数等于 $n - id + 1 - (cnt == 0)$。
#include <iostream>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int n, q, id, cnt, a[N];
LL k, sum[N];
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
sum[i] = sum[i - 1] + a[i];
}
while (q--) {
scanf("%lld", &k);
if (k >= sum[n] - sum[id] + cnt) {
id = cnt = 0;
} else {
int l = id, r = n;
while (l < r) {
int m = l + r >> 1;
if (sum[m] - sum[id] + cnt >= k) r = m;
else l = m + 1;
}
cnt = sum[l] - sum[id] + cnt - k;
id = l;
}
printf("%d\n", n - id + !!cnt);
}
return 0;
}
做法二
当餐厅的客人总数确定时,能坐满多少张桌子是确定的,并且后者关于前者单调递增(有单调性必有二段性,反之不成立),因此可维护当前客人总数,每次二分找到最后一张被坐满的桌号 $i$,则没被坐满的桌子数量为 $n - i$。
#include <iostream>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int n, q;
LL k, guest, sum[N];
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", sum + i);
sum[i] += sum[i - 1];
}
while (q--) {
scanf("%lld", &k);
guest += k;
if (guest >= sum[n]) guest = 0;
int l = 0, r = n;
while (l < r) {
int m = l + r + 1 >> 1;
if (sum[m] <= guest) l = m;
else r = m - 1;
}
printf("%d\n", n - l);
}
return 0;
}