力扣（leetcode）每日一题 2286 以组为单位订音乐会的门票 | 线段树
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
// 总共只剩下 1 个座位。
提示：
1 <= n <= 5 * 1041 <= m, k <= 1090 <= maxRow <= n - 1gather和scatter总 调用次数不超过5 * 104次。
题解1
这里实现的时候，我还不会线段树。硬是通过小优化使得提交通过
class BookMyShow {int totalRow;int[] arr;int jump = 0;long totalCount;public BookMyShow (int n, int m) {// 需要加快更新的频率arr = new int[n];totalRow = m;totalCount = (long) n * m;}public int[] gather(int k, int maxRow) {// 快速失败if (k > totalRow) {return new int[0];}for (int i = jump; i <= maxRow; i++) {// 计算是否放得下if (arr[i] + k <= totalRow) {int[] res = new int[]{i, arr[i]};arr[i] = arr[i] + k;// 没有问题totalCount -= k;return res;}}return new int[0];}public boolean scatter(int k, int maxRow) {if (totalCount < k) {return false;}int count = 0;boolean flag = false;int index = 0;for (int i = jump; i <= maxRow; i++) {count += totalRow - arr[i];if (count >= k) {flag = true;index = i;break;}}if (!flag) {return false;}// 可以省略
// for (int i = jump; i < index; i++) {
// arr[i] = totalRow;
// }jump = index;// 多累计了3人，需要减去arr[index] = totalRow - (count - k);totalCount -= k;return true;}
}题解2
这里的线段树应该不是最优解，不然这里的数值不会这么难看
但是我没有精力去精进
因为用前面题解的模板来改写
class Solution2286 { public static void main(String[] args) { BookMyShow bookMyShow = new BookMyShow(5, 9); // 假设是9个位置 bookMyShow.scatter(9, 1); bookMyShow.scatter(1, 3); bookMyShow.gather(3, 4); bookMyShow.gather(1, 1); bookMyShow.gather(10, 4); } static class BookMyShow { int totalSpace; int[] arr; long[] sumArr; int[] minArr; int right; int left = 1; int root = 1; public BookMyShow(int n, int m) { right = n; int length = n + 1; arr = new int[length]; sumArr = new long[4 * length]; // 这里加速了范围上累加和的查询 minArr = new int[4 * length]; // 这里加速了范围上最小值的查询 totalSpace = m; } public int[] gather(int k, int maxRow) { maxRow++; int min = getMin(left, right, root, totalSpace - k);// 9 个位置 来了5个 需要找小于等于4的 if (min > maxRow) { return new int[0]; } // 查询当前min的值 long query = query(min, min); // 更新当前min的值 update(min, min, (int) query + k); return new int[]{min - 1, (int) query}; } // 9871 9 只要找到小于9的行就可以进行增加了 public boolean scatter(int k, int maxRow) { maxRow++; // 计算和 long res = query(1, maxRow); // 当这里的累计大于k的时候就可以入座 if (res + k > (long) (maxRow) * totalSpace) { return false; } // 9 个位置 只要是小于9的就可以了，查询小于等于8的 int min = getMin(left, right, root, totalSpace - 1); while (true) { int query = (int) query(min, min); if (query + k <= totalSpace) { // 当前排的位置可以把人安排了就安排入座 update(min, min, k + query); // 这里需要k+min return true; } // 更新 update(min, min, totalSpace); k -= (totalSpace - query);// 这里查询到4个，那么可以安排 5个入座。计算就是9-4 min = getMin(left, right, root, totalSpace - 1); } } public int getMin(int left, int right, int node, int value) { if (left == right) { if (minArr[node] > value) { // 没有 return Integer.MAX_VALUE; } return left; } int mid = (left + right) / 2; if (minArr[node * 2] <= value) { return getMin(left, mid, node * 2, value); } else { return getMin(mid + 1, right, node * 2 + 1, value); } } public long query(int start, int end) { return query(start, end, left, right, root); } public long query(int start, int end, int left, int right, int node) { if (start <= left && right <= end) { return sumArr[node]; } int mid = (left + right) / 2; long total = 0; if (start <= mid) { // 下发左边 total += query(start, end, left, mid, node * 2); } if (end > mid) { // 下发右边 total += query(start, end, mid + 1, right, node * 2 + 1); } return total; } public void update(int start, int end, int value) { update(start, end, value, left, right, root); } // 模板是范围上更新，但是这里的实际情况是单点更新public void update(int start, int end, int value, int left, int right, int node) { if (start <= left && right <= end) { sumArr[node] = value; minArr[node] = value; return; } int mid = (left + right) / 2; if (start <= mid) { // 下发左边 update(start, end, value, left, mid, node * 2); } if (end > mid) { // 下发右边 update(start, end, value, mid + 1, right, node * 2 + 1); } // 刷新求和 sumArr[node] = sumArr[node * 2] + sumArr[node * 2 + 1]; // 刷新最小 minArr[node] = Math.min(minArr[node * 2], minArr[node * 2 + 1]); } } }
总结
minArr的使用是超出了模板的范围
// 刷新求和
sumArr[node] = sumArr[node * 2] + sumArr[node * 2 + 1];
// 刷新最小
minArr[node] = Math.min(minArr[node * 2], minArr[node * 2 + 1]); 这些值的刷新，在递归前，还是递归后，还是递归方法的尽头。都是有讲究的