LeetCode 2286. Booking Concert Tickets in Groups - C实现一、完整实现可直接提交#include vector #include algorithm #include functional using namespace std; class BookMyShow { private: int n, m; vectorlong long sum; // 区间内空闲座位总数 vectorint max_seat; // 区间内最大连续空闲座位数 // 更新节点信息 void pushUp(int node) { sum[node] sum[node * 2] sum[node * 2 1]; max_seat[node] max(max_seat[node * 2], max_seat[node * 2 1]); } // 建树 void build(int node, int l, int r) { if (l r) { sum[node] m; max_seat[node] m; return; } int mid (l r) 1; build(node * 2, l, mid); build(node * 2 1, mid 1, r); pushUp(node); } // 查询区间最大连续空闲座位数 int queryMax(int node, int l, int r, int ql, int qr) { if (ql l r qr) { return max_seat[node]; } int mid (l r) 1; int res 0; if (ql mid) { res max(res, queryMax(node * 2, l, mid, ql, qr)); } if (qr mid) { res max(res, queryMax(node * 2 1, mid 1, r, ql, qr)); } return res; } // 查询区间空闲座位总数 long long querySum(int node, int l, int r, int ql, int qr) { if (ql l r qr) { return sum[node]; } int mid (l r) 1; long long res 0; if (ql mid) { res querySum(node * 2, l, mid, ql, qr); } if (qr mid) { res querySum(node * 2 1, mid 1, r, ql, qr); } return res; } // 找到第一个有k个连续空闲座位的行 int findRow(int node, int l, int r, int ql, int qr, int k) { if (l r) { return l; } int mid (l r) 1; if (ql mid max_seat[node * 2] k) { return findRow(node * 2, l, mid, ql, qr, k); } return findRow(node * 2 1, mid 1, r, ql, qr, k); } // 在指定行预定k个连续座位 int bookRow(int node, int l, int r, int row, int k, int start) { if (l r) { start m - (int)sum[node]; sum[node] - k; max_seat[node] (int)sum[node]; return start; } int mid (l r) 1; if (row mid) { bookRow(node * 2, l, mid, row, k, start); } else { bookRow(node * 2 1, mid 1, r, row, k, start); } pushUp(node); return start; } // 分散分配座位 int scatterSeats(int node, int l, int r, int ql, int qr, int k) { if (k 0) return 0; if (l r) { int take min((long long)k, sum[node]); sum[node] - take; max_seat[node] (int)sum[node]; return take; } int mid (l r) 1; int taken 0; // 先分配左子树 if (ql mid k 0) { taken scatterSeats(node * 2, l, mid, ql, qr, k); k - taken; } // 再分配右子树 if (qr mid k 0) { taken scatterSeats(node * 2 1, mid 1, r, ql, qr, k); } pushUp(node); return taken; } public: BookMyShow(int n, int m) { this-n n; this-m m; sum.resize(4 * n); max_seat.resize(4 * n); build(1, 0, n - 1); } // 同一排连续k个座位 vectorint gather(int k, int maxRow) { if (queryMax(1, 0, n - 1, 0, maxRow) k) { return {}; } int row findRow(1, 0, n - 1, 0, maxRow, k); int start 0; bookRow(1, 0, n - 1, row, k, start); return {row, start}; } // 不要求连续尽量往前占 bool scatter(int k, int maxRow) { if (querySum(1, 0, n - 1, 0, maxRow) k) { return false; } scatterSeats(1, 0, n - 1, 0, maxRow, k); return true; } };二、更简洁的线段树实现STL版#include vector #include functional using namespace std; class BookMyShow { private: int n, m; vectorlong long tree_sum; // 区间和线段树 vectorint tree_max; // 区间最大值线段树 // 更新节点 void pushup(int idx) { tree_sum[idx] tree_sum[idx 1] tree_sum[idx 1 | 1]; tree_max[idx] max(tree_max[idx 1], tree_max[idx 1 | 1]); } // 建树 void build(int idx, int l, int r) { if (l r) { tree_sum[idx] m; tree_max[idx] m; return; } int mid (l r) 1; build(idx 1, l, mid); build(idx 1 | 1, mid 1, r); pushup(idx); } // 区间查询最大连续空位 int query_max(int idx, int l, int r, int ql, int qr) { if (ql l r qr) return tree_max[idx]; int mid (l r) 1; int res 0; if (ql mid) res max(res, query_max(idx 1, l, mid, ql, qr)); if (qr mid) res max(res, query_max(idx 1 | 1, mid 1, r, ql, qr)); return res; } // 区间查询空闲座位总数 long long query_sum(int idx, int l, int r, int ql, int qr) { if (ql l r qr) return tree_sum[idx]; int mid (l r) 1; long long res 0; if (ql mid) res query_sum(idx 1, l, mid, ql, qr); if (qr mid) res query_sum(idx 1 | 1, mid 1, r, ql, qr); return res; } // 找到第一个有k个连续空位的行 int find_first(int idx, int l, int r, int ql, int qr, int k) { if (l r) return l; int mid (l r) 1; if (ql mid tree_max[idx 1] k) return find_first(idx 1, l, mid, ql, qr, k); return find_first(idx 1 | 1, mid 1, r, ql, qr, k); } // 在指定行预定k个连续座位 int book(int idx, int l, int r, int row, int k) { if (l r) { int start m - (int)tree_sum[idx]; tree_sum[idx] - k; tree_max[idx] (int)tree_sum[idx]; return start; } int mid (l r) 1; int res 0; if (row mid) res book(idx 1, l, mid, row, k); else res book(idx 1 | 1, mid 1, r, row, k); pushup(idx); return res; } // 分散分配座位 void scatter(int idx, int l, int r, int ql, int qr, int k) { if (k 0) return; if (l r) { int take min((long long)k, tree_sum[idx]); tree_sum[idx] - take; tree_max[idx] (int)tree_sum[idx]; k - take; return; } int mid (l r) 1; if (ql mid) scatter(idx 1, l, mid, ql, qr, k); if (k 0 qr mid) scatter(idx 1 | 1, mid 1, r, ql, qr, k); pushup(idx); } public: BookMyShow(int n, int m) : n(n), m(m) { tree_sum.resize(4 * n); tree_max.resize(4 * n); build(1, 0, n - 1); } vectorint gather(int k, int maxRow) { if (query_max(1, 0, n - 1, 0, maxRow) k) return {}; int row find_first(1, 0, n - 1, 0, maxRow, k); int start book(1, 0, n - 1, row, k); return {row, start}; } bool scatter(int k, int maxRow) { if (query_sum(1, 0, n - 1, 0, maxRow) k) return false; scatter(1, 0, n - 1, 0, maxRow, k); return true; } };三、使用结构体的清晰实现#include vector using namespace std; struct Node { long long sum; // 空闲座位总数 int max_seat; // 最大连续空闲座位数 Node() : sum(0), max_seat(0) {} Node(long long s, int m) : sum(s), max_seat(m) {} }; class BookMyShow { private: int n, m; vectorNode tree; Node merge(const Node a, const Node b) { return Node(a.sum b.sum, max(a.max_seat, b.max_seat)); } void build(int idx, int l, int r) { if (l r) { tree[idx] Node(m, m); return; } int mid (l r) / 2; build(idx * 2, l, mid); build(idx * 2 1, mid 1, r); tree[idx] merge(tree[idx * 2], tree[idx * 2 1]); } Node query(int idx, int l, int r, int ql, int qr) { if (ql l r qr) return tree[idx]; int mid (l r) / 2; Node res(0, 0); if (ql mid) res merge(res, query(idx * 2, l, mid, ql, qr)); if (qr mid) res merge(res, query(idx * 2 1, mid 1, r, ql, qr)); return res; } int findRow(int idx, int l, int r, int ql, int qr, int k) { if (l r) return l; int mid (l r) / 2; if (ql mid tree[idx * 2].max_seat k) return findRow(idx * 2, l, mid, ql, qr, k); return findRow(idx * 2 1, mid 1, r, ql, qr, k); } int bookRow(int idx, int l, int r, int row, int k) { if (l r) { int start m - (int)tree[idx].sum; tree[idx].sum - k; tree[idx].max_seat (int)tree[idx].sum; return start; } int mid (l r) / 2; int res 0; if (row mid) res bookRow(idx * 2, l, mid, row, k); else res bookRow(idx * 2 1, mid 1, r, row, k); tree[idx] merge(tree[idx * 2], tree[idx * 2 1]); return res; } int scatterSeats(int idx, int l, int r, int ql, int qr, int k) { if (k 0) return 0; if (l r) { int take min((long long)k, tree[idx].sum); tree[idx].sum - take; tree[idx].max_seat (int)tree[idx].sum; return take; } int mid (l r) / 2; int taken 0; if (ql mid) { taken scatterSeats(idx * 2, l, mid, ql, qr, k); k - taken; } if (qr mid k 0) { taken scatterSeats(idx * 2 1, mid 1, r, ql, qr, k); } tree[idx] merge(tree[idx * 2], tree[idx * 2 1]); return taken; } public: BookMyShow(int n, int m) : n(n), m(m) { tree.resize(4 * n); build(1, 0, n - 1); } vectorint gather(int k, int maxRow) { if (query(1, 0, n - 1, 0, maxRow).max_seat k) { return {}; } int row findRow(1, 0, n - 1, 0, maxRow, k); int start bookRow(1, 0, n - 1, row, k); return {row, start}; } bool scatter(int k, int maxRow) { if (query(1, 0, n - 1, 0, maxRow).sum k) { return false; } scatterSeats(1, 0, n - 1, 0, maxRow, k); return true; } };四、复杂度分析操作时间复杂度空间复杂度构造函数O(n)O(n)gatherO(log n)O(1)scatterO(log n)O(1)五、核心思路总结线段树维护每个节点维护两个信息区间内空闲座位总数用于 scatter 操作区间内最大连续空闲座位数用于 gather 操作gather 操作查询 [0, maxRow] 区间内是否有连续 k 个空位找到第一个满足条件的行在该行分配 k 个连续座位返回行号和起始座位号scatter 操作查询 [0, maxRow] 区间内是否有至少 k 个空位从左到右逐行分配直到分配完 k 个座位返回是否分配成功关键优化使用线段树实现 O(log n) 的查询和更新通过二分查找快速定位满足条件的行scatter 操作通过递归分配避免 O(k) 的复杂度