2286. 以组为单位订音乐会的门票
一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：
k 位观众坐在 同一排座位，且座位连续 。k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。由于观众非常挑剔，所以：
maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。请你实现 BookMyShow 类：
BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。
示例 1：
输入：
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]
解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]
// 这一组安排第 0 排 [0, 3] 的座位。
bms.gather(2, 0); // 返回 []
// 第 0 排只剩下 1 个座位。
// 所以无法安排 2 个连续座位。
bms.scatter(5, 1); // 返回 True
// 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
bms.scatter(5, 1); // 返回 False
// 总共只剩下 2 个座位。
提示：
1 <= n <= 5 * 1041 <= m, k <= 1090 <= maxRow <= n - 1gather 和 scatter 总 调用次数不超过 5 * 104 次。原站题解
javascript 解法, 执行用时: 532 ms, 内存消耗: 80.2 MB, 提交时间: 2024-09-28 23:32:22
class BookMyShow {
constructor(n, m) {
this.n = n;
this.m = m;
const size = 2 << (32 - Math.clz32(n)); // 比 4n 更小
this.min = Array(size).fill(0);
this.sum = Array(size).fill(0);
}
// 把下标 i 上的元素值增加 val
update(o, l, r, i, val) {
if (l === r) {
this.min[o] += val;
this.sum[o] += val;
return;
}
const m = Math.floor((l + r) / 2);
if (i <= m) {
this.update(o * 2, l, m, i, val);
} else {
this.update(o * 2 + 1, m + 1, r, i, val);
}
this.min[o] = Math.min(this.min[o * 2], this.min[o * 2 + 1]);
this.sum[o] = this.sum[o * 2] + this.sum[o * 2 + 1];
}
// 返回区间 [L,R] 内的元素和
querySum(o, l, r, L, R) {
if (L <= l && r <= R) {
return this.sum[o];
}
let res = 0;
const m = Math.floor((l + r) / 2);
if (L <= m) {
res = this.querySum(o * 2, l, m, L, R);
}
if (R > m) {
res += this.querySum(o * 2 + 1, m + 1, r, L, R);
}
return res;
}
// 返回区间 [0,R] 中 <= val 的最靠左的位置，不存在时返回 -1
findFirst(o, l, r, R, val) {
if (this.min[o] > val) {
return -1; // 整个区间的元素值都大于 val
}
if (l === r) {
return l;
}
const m = Math.floor((l + r) / 2);
if (this.min[o * 2] <= val) {
return this.findFirst(o * 2, l, m, R, val);
}
if (R > m) {
return this.findFirst(o * 2 + 1, m + 1, r, R, val);
}
return -1;
}
gather(k, maxRow) {
// 找第一个能倒入 k 升水的水桶
const r = this.findFirst(1, 0, this.n - 1, maxRow, this.m - k);
if (r < 0) { // 没有这样的水桶
return [];
}
const c = this.querySum(1, 0, this.n - 1, r, r);
this.update(1, 0, this.n - 1, r, k); // 倒水
return [r, c];
}
scatter(k, maxRow) {
// [0,maxRow] 的接水量之和
const s = this.querySum(1, 0, this.n - 1, 0, maxRow);
if (s > this.m * (maxRow + 1) - k) {
return false; // 水桶已经装了太多的水
}
// 从第一个没有装满的水桶开始
let i = this.findFirst(1, 0, this.n - 1, maxRow, this.m - 1);
while (k) {
const left = Math.min(this.m - this.querySum(1, 0, this.n - 1, i, i), k);
this.update(1, 0, this.n - 1, i, left); // 倒水
k -= left;
i++;
}
return true;
}
}
/**
* Your BookMyShow object will be instantiated and called as such:
* var obj = new BookMyShow(n, m)
* var param_1 = obj.gather(k,maxRow)
* var param_2 = obj.scatter(k,maxRow)
*/
golang 解法, 执行用时: 424 ms, 内存消耗: 36 MB, 提交时间: 2023-10-08 22:53:56
type seg []struct{ l, r, min, sum int }
func (t seg) build(o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
return
}
m := (l + r) >> 1
t.build(o<<1, l, m)
t.build(o<<1|1, m+1, r)
}
// 将 idx 上的元素值增加 val
func (t seg) add(o, idx, val int) {
if t[o].l == t[o].r {
t[o].min += val
t[o].sum += val
return
}
m := (t[o].l + t[o].r) >> 1
if idx <= m {
t.add(o<<1, idx, val)
} else {
t.add(o<<1|1, idx, val)
}
lo, ro := t[o<<1], t[o<<1|1]
t[o].min = min(lo.min, ro.min)
t[o].sum = lo.sum + ro.sum
}
// 返回区间 [l,r] 内的元素和
func (t seg) querySum(o, l, r int) (sum int) {
if l <= t[o].l && t[o].r <= r {
return t[o].sum
}
m := (t[o].l + t[o].r) >> 1
if l <= m {
sum += t.querySum(o<<1, l, r)
}
if r > m {
sum += t.querySum(o<<1|1, l, r)
}
return
}
// 返回区间 [1,R] 中 <= val 的最靠左的位置，不存在时返回 0
func (t seg) index(o, r, val int) int {
if t[o].min > val { // 说明整个区间的元素值都大于 val
return 0
}
if t[o].l == t[o].r {
return t[o].l
}
m := (t[o].l + t[o].r) >> 1
if t[o<<1].min <= val { // 看看左半部分
return t.index(o<<1, r, val)
}
if m < r { // 看看右半部分
return t.index(o<<1|1, r, val)
}
return 0
}
type BookMyShow struct {
seg
m int
}
func Constructor(n, m int) BookMyShow {
t := make(seg, n*4)
t.build(1, 1, n)
return BookMyShow{t, m}
}
func (t BookMyShow) Gather(k, maxRow int) []int {
i := t.index(1, maxRow+1, t.m-k)
if i == 0 { // 不存在
return nil
}
seats := t.querySum(1, i, i)
t.add(1, i, k) // 占据 k 个座位
return []int{i - 1, seats}
}
func (t BookMyShow) Scatter(k, maxRow int) bool {
if (maxRow+1)*t.m-t.querySum(1, 1, maxRow+1) < k { // 剩余座位不足 k 个
return false
}
// 从第一个没有坐满的排开始占座
for i := t.index(1, maxRow+1, t.m-1); ; i++ {
leftSeats := t.m - t.querySum(1, i, i)
if k <= leftSeats { // 剩余人数不够坐后面的排
t.add(1, i, k)
return true
}
k -= leftSeats
t.add(1, i, leftSeats)
}
}
func min(a, b int) int { if a > b { return b }; return a }
/**
* Your BookMyShow object will be instantiated and called as such:
* obj := Constructor(n, m);
* param_1 := obj.Gather(k,maxRow);
* param_2 := obj.Scatter(k,maxRow);
*/
cpp 解法, 执行用时: 596 ms, 内存消耗: 283.4 MB, 提交时间: 2023-10-08 22:53:21
class BookMyShow {
int n, m;
vector<int> min;
vector<long> sum;
// 将 idx 上的元素值增加 val
void add(int o, int l, int r, int idx, int val) {
if (l == r) {
min[o] += val;
sum[o] += val;
return;
}
int m = (l + r) / 2;
if (idx <= m) add(o * 2, l, m, idx, val);
else add(o * 2 + 1, m + 1, r, idx, val);
min[o] = std::min(min[o * 2], min[o * 2 + 1]);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
}
// 返回区间 [L,R] 内的元素和
long query_sum(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
if (L <= l && r <= R) return sum[o];
long sum = 0L;
int m = (l + r) / 2;
if (L <= m) sum += query_sum(o * 2, l, m, L, R);
if (R > m) sum += query_sum(o * 2 + 1, m + 1, r, L, R);
return sum;
}
// 返回区间 [1,R] 中 <= val 的最靠左的位置，不存在时返回 0
int index(int o, int l, int r, int R, int val) { // R 在整个递归过程中均不变，将其大写，视作常量
if (min[o] > val) return 0; // 说明整个区间的元素值都大于 val
if (l == r) return l;
int m = (l + r) / 2;
if (min[o * 2] <= val) return index(o * 2, l, m, R, val); // 看看左半部分
if (m < R) return index(o * 2 + 1, m + 1, r, R, val); // 看看右半部分
return 0;
}
public:
BookMyShow(int n, int m) : n(n), m(m), min(n * 4), sum(n * 4) {}
vector<int> gather(int k, int maxRow) {
int i = index(1, 1, n, maxRow + 1, m - k);
if (i == 0) return {}; // 不存在
int seats = query_sum(1, 1, n, i, i);
add(1, 1, n, i, k); // 占据 k 个座位
return {i - 1, seats};
}
bool scatter(int k, int maxRow) {
if ((long) (maxRow + 1) * m - query_sum(1, 1, n, 1, maxRow + 1) < k) return false; // 剩余座位不足 k 个
// 从第一个没有坐满的排开始占座
for (int i = index(1, 1, n, maxRow + 1, m - 1);; ++i) {
int left_seats = m - query_sum(1, 1, n, i, i);
if (k <= left_seats) { // 剩余人数不够坐后面的排
add(1, 1, n, i, k);
return true;
}
k -= left_seats;
add(1, 1, n, i, left_seats);
}
}
};
/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow* obj = new BookMyShow(n, m);
* vector<int> param_1 = obj->gather(k,maxRow);
* bool param_2 = obj->scatter(k,maxRow);
*/
java 解法, 执行用时: 140 ms, 内存消耗: 76.2 MB, 提交时间: 2023-10-08 22:53:02
class BookMyShow {
int n, m;
int[] min;
long[] sum;
public BookMyShow(int n, int m) {
this.n = n;
this.m = m;
min = new int[n * 4];
sum = new long[n * 4];
}
public int[] gather(int k, int maxRow) {
int i = index(1, 1, n, maxRow + 1, m - k);
if (i == 0) return new int[]{}; // 不存在
var seats = (int) query_sum(1, 1, n, i, i);
add(1, 1, n, i, k); // 占据 k 个座位
return new int[]{i - 1, seats};
}
public boolean scatter(int k, int maxRow) {
if ((long) (maxRow + 1) * m - query_sum(1, 1, n, 1, maxRow + 1) < k) return false; // 剩余座位不足 k 个
// 从第一个没有坐满的排开始占座
for (var i = index(1, 1, n, maxRow + 1, m - 1); ; ++i) {
var left_seats = m - (int) query_sum(1, 1, n, i, i);
if (k <= left_seats) { // 剩余人数不够坐后面的排
add(1, 1, n, i, k);
return true;
}
k -= left_seats;
add(1, 1, n, i, left_seats);
}
}
// 将 idx 上的元素值增加 val
void add(int o, int l, int r, int idx, int val) {
if (l == r) {
min[o] += val;
sum[o] += val;
return;
}
var m = (l + r) / 2;
if (idx <= m) add(o * 2, l, m, idx, val);
else add(o * 2 + 1, m + 1, r, idx, val);
min[o] = Math.min(min[o * 2], min[o * 2 + 1]);
sum[o] = sum[o * 2] + sum[o * 2 + 1];
}
// 返回区间 [L,R] 内的元素和
long query_sum(int o, int l, int r, int L, int R) { // L 和 R 在整个递归过程中均不变，将其大写，视作常量
if (L <= l && r <= R) return sum[o];
var sum = 0L;
var m = (l + r) / 2;
if (L <= m) sum += query_sum(o * 2, l, m, L, R);
if (R > m) sum += query_sum(o * 2 + 1, m + 1, r, L, R);
return sum;
}
// 返回区间 [1,R] 中 <= val 的最靠左的位置，不存在时返回 0
int index(int o, int l, int r, int R, int val) { // R 在整个递归过程中均不变，将其大写，视作常量
if (min[o] > val) return 0; // 说明整个区间的元素值都大于 val
if (l == r) return l;
var m = (l + r) / 2;
if (min[o * 2] <= val) return index(o * 2, l, m, R, val); // 看看左半部分
if (m < R) return index(o * 2 + 1, m + 1, r, R, val); // 看看右半部分
return 0;
}
}
/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow obj = new BookMyShow(n, m);
* int[] param_1 = obj.gather(k,maxRow);
* boolean param_2 = obj.scatter(k,maxRow);
*/
python3 解法, 执行用时: 2396 ms, 内存消耗: 48.2 MB, 提交时间: 2023-10-08 22:52:48
class BookMyShow:
def __init__(self, n: int, m: int):
self.n = n
self.m = m
self.min = [0] * (n * 4)
self.sum = [0] * (n * 4)
# 将 idx 上的元素值增加 val
def add(self, o: int, l: int, r: int, idx: int, val: int) -> None:
if l == r:
self.min[o] += val
self.sum[o] += val
return
m = (l + r) // 2
if idx <= m: self.add(o * 2, l, m, idx, val)
else: self.add(o * 2 + 1, m + 1, r, idx, val)
self.min[o] = min(self.min[o * 2], self.min[o * 2 + 1])
self.sum[o] = self.sum[o * 2] + self.sum[o * 2 + 1]
# 返回区间 [L,R] 内的元素和
def query_sum(self, o: int, l: int, r: int, L: int, R: int) -> int:
if L <= l and r <= R: return self.sum[o]
sum = 0
m = (l + r) // 2
if L <= m: sum += self.query_sum(o * 2, l, m, L, R)
if R > m: sum += self.query_sum(o * 2 + 1, m + 1, r, L, R)
return sum
# 返回区间 [1,R] 中 <= val 的最靠左的位置，不存在时返回 0
def index(self, o: int, l: int, r: int, R: int, val: int) -> int:
if self.min[o] > val: return 0 # 说明整个区间的元素值都大于 val
if l == r: return l
m = (l + r) // 2
if self.min[o * 2] <= val: return self.index(o * 2, l, m, R, val) # 看看左半部分
if m < R: return self.index(o * 2 + 1, m + 1, r, R, val) # 看看右半部分
return 0
def gather(self, k: int, maxRow: int) -> List[int]:
i = self.index(1, 1, self.n, maxRow + 1, self.m - k)
if i == 0: return []
seats = self.query_sum(1, 1, self.n, i, i)
self.add(1, 1, self.n, i, k) # 占据 k 个座位
return [i - 1, seats]
def scatter(self, k: int, maxRow: int) -> bool:
if (maxRow + 1) * self.m - self.query_sum(1, 1, self.n, 1, maxRow + 1) < k:
return False # 剩余座位不足 k 个
i = self.index(1, 1, self.n, maxRow + 1, self.m - 1) # 从第一个没有坐满的排开始占座
while True:
left_seats = self.m - self.query_sum(1, 1, self.n, i, i)
if k <= left_seats: # 剩余人数不够坐后面的排
self.add(1, 1, self.n, i, k)
return True
k -= left_seats
self.add(1, 1, self.n, i, left_seats)
i += 1
# Your BookMyShow object will be instantiated and called as such:
# obj = BookMyShow(n, m)
# param_1 = obj.gather(k,maxRow)
# param_2 = obj.scatter(k,maxRow)