当前位置：首页 > news >正文

力扣题解2286

news 来源：原创 2024/9/29 9:22:44

大家好，欢迎来到无限大的频道

今天继续给大家带来力扣题解

题目描述（困难）：

以组为单位订音乐会的门票
一个音乐会总共有 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 。

这道题目中，我们需要设计一个较为复杂的座位安排系统，这里我们使用线段树来维护我们需要的数据 —— 每排座位的最小已坐座位数和已坐座位数之和。我们需要实现两个主要功能：gather和scatter。这两个方法分别按照题目要求，在条件限制下分配座位，并返回相应的结果。

题目解析

gather功能：
- 要求找到一排能容纳k个连续座位的位置。
- 搜索范围是从第0排到maxRow排。
- 优先选择排数最小且符合条件的排。
- 返回该排的行数及第一个座位的编号。
scatter功能：
- 不要求连续，但需要在规定排数内找到足够的k个座位。
- 搜索范围是从第0排到maxRow排。
- 在每个排中尽可能填充座位（优先选择排数最小的）。

解题思路

为了高效地管理每排座位的状态，使用了两棵线段树：

minTree：维护的是每个区间最小的已用座位数。这帮助我们快速找到满足条件的最小排。
sumTree：维护的是每个区间已用座位数的和。这帮助我们快速计算一个区间内的填充情况。

理解minTree和sumTree的区别对于掌握线段树的应用非常重要。在这道题中，我们需要管理每排座位的状态来满足gather和scatter需求。让我们逐个解释这两个概念及其用途。

`minTree`

定义：minTree 维护的是一个区间内的最小已用座位数。也就是说，它能够快速查询某一范围（例如某几排）内哪个排的座位使用情况是最少的。
用途：通过查询minTree，我们可以快速找到满足gather条件的最小排（例如，已用座位数小于等于 m - k），这帮助我们高效地找到哪个排还能够再容纳更多的座位，并且确保所选排是可用的、最优的。

例如，当我们要分配k个连续的座位时，我们首先需要找到最小的已用座位数（used）小于等于 m - k 的行。如果某行的已用座位数少于这个值，那么它就是一个合适的选择。

`sumTree`

定义：sumTree 维护的是一个区间内已用座位数的总和。它能够快速计算某一范围（例如多排座位的）的已用座位总数。
用途：在处理scatter时，我们需要知道在某一范围内的总已用座位数。通过查询sumTree，我们可以快速计算这些座位的总数，从而与总座位数进行比较，以判断是否能满足新的需求。

例如，考虑scatter功能时，我们需要查看从第0排到maxRow排的总已用座位数（usedTotal）。我们用这个值来判断在此区间内是否可以再安排k个座位。这也是确保在满足条件下分配座位的必要步骤。

我们主要需要实现以下几个方法：

修改方法 (modify)：
- 通过更新线段树节点，以反映座位占用的变化。
- 对一个排添加座位数，更新 minTree 和 sumTree。
查询最小值方法 (queryMinRow)：
- 用来找到满足条件的最小排。
查询总和方法 (querySum)：
- 用来计算给定区间的已用座位总和。

代码分析

结合思路，我们有以下详细的C语言和C++实现：

C语言实现

typedef struct {int n; // The number of rowsint m; // Seats per rowint *minTree; // Segment tree for minimum occupied seats in a rangelong long *sumTree; // Segment tree for sum of occupied seats in a range
} BookMyShow;BookMyShow *bookMyShowCreate(int n, int m) {BookMyShow *obj = (BookMyShow*)malloc(sizeof(BookMyShow));obj->n = n;obj->m = m;obj->minTree = (int*)malloc(sizeof(int) * (4 * n));obj->sumTree = (long long*)malloc(sizeof(long long) * (4 * n));memset(obj->minTree, 0, sizeof(int) * (4 * n));memset(obj->sumTree, 0, sizeof(long long) * (4 * n));return obj;
}void modify(BookMyShow *obj, int i, int l, int r, int index, int val) {if (l == r) {obj->minTree[i] = val;obj->sumTree[i] = val;return;}int mid = (l + r) / 2;if (index <= mid) {modify(obj, i * 2, l, mid, index, val);} else {modify(obj, i * 2 + 1, mid + 1, r, index, val);}obj->minTree[i] = obj->minTree[i * 2] < obj->minTree[i * 2 + 1] ? obj->minTree[i * 2] : obj->minTree[i * 2 + 1];obj->sumTree[i] = obj->sumTree[i * 2] + obj->sumTree[i * 2 + 1];
}int queryMinRow(BookMyShow *obj, int i, int l, int r, int val) {if (l == r) {if (obj->minTree[i] > val) {return obj->n;}return l;}int mid = (l + r) / 2;if (obj->minTree[i * 2] <= val) {return queryMinRow(obj, i * 2, l, mid, val);} else {return queryMinRow(obj, i * 2 + 1, mid + 1, r, val);}
}long long querySum(BookMyShow *obj, int i, int l, int r, int l2, int r2) {if (r < l2 || l > r2) {return 0;}if (l >= l2 && r <= r2) {return obj->sumTree[i];}int mid = (l + r) / 2;return querySum(obj, i * 2, l, mid, l2, r2) + querySum(obj, i * 2 + 1, mid + 1, r, l2, r2);
}int *bookMyShowGather(BookMyShow *obj, int k, int maxRow, int *retSize) {int i = queryMinRow(obj, 1, 0, obj->n - 1, obj->m - k);if (i > maxRow) {*retSize = 0;return NULL;}int used = querySum(obj, 1, 0, obj->n - 1, i, i);modify(obj, 1, 0, obj->n - 1, i, used + k);int *ret = (int *)malloc(sizeof(int) * 2);ret[0] = i;ret[1] = used;*retSize = 2;return ret;
}bool bookMyShowScatter(BookMyShow *obj, int k, int maxRow) {long long usedTotal = querySum(obj, 1, 0, obj->n - 1, 0, maxRow);if ((maxRow + 1LL) * obj->m - usedTotal < k) {return false;}int i = queryMinRow(obj, 1, 0, obj->n - 1, obj->m - 1);while (k > 0) {int used = querySum(obj, 1, 0, obj->n - 1, i, i);if (obj->m - used >= k) {modify(obj, 1, 0, obj->n - 1, i, used + k);break;}k -= obj->m - used;modify(obj, 1, 0, obj->n - 1, i, obj->m);i++;}return true;
}void bookMyShowFree(BookMyShow *obj) {free(obj->minTree);free(obj->sumTree);free(obj);
}

C++版本实现

class BookMyShow {
private:int n, m;vector<int> minTree;vector<long long> sumTree;void modify(int i, int l, int r, int index, int val) {if (l == r) {minTree[i] = val;sumTree[i] = val;return;}int mid = (l + r) / 2;if (index <= mid) {modify(i * 2, l, mid, index, val);} else {modify(i * 2 + 1, mid + 1, r, index, val);}minTree[i] = min(minTree[i * 2], minTree[i * 2 + 1]);sumTree[i] = sumTree[i * 2] + sumTree[i * 2 + 1];}int queryMinRow(int i, int l, int r, int val) {if (l == r) return minTree[i] > val ? n : l;int mid = (l + r) / 2;if (minTree[i * 2] <= val) {return queryMinRow(i * 2, l, mid, val);} else {return queryMinRow(i * 2 + 1, mid + 1, r, val);}}long long querySum(int i, int l, int r, int l2, int r2) {if (l2 <= l && r <= r2) return sumTree[i];int mid = (l + r) / 2;long long sum = 0;if (mid >= l2) sum += querySum(i * 2, l, mid, l2, r2);if (mid < r2) sum += querySum(i * 2 + 1, mid + 1, r, l2, r2);return sum;}public:BookMyShow(int n, int m): n(n), m(m), minTree(4 * n, 0), sumTree(4 * n, 0) {}vector<int> gather(int k, int maxRow) {int i = queryMinRow(1, 0, n - 1, m - k);if (i > maxRow) return {};int used = querySum(1, 0, n - 1, i, i);modify(1, 0, n - 1, i, used + k);return {i, used};}bool scatter(int k, int maxRow) {long long usedTotal = querySum(1, 0, n - 1, 0, maxRow);if ((long long)(maxRow + 1) * m - usedTotal < k) return false;int i = queryMinRow(1, 0, n - 1, m - 1);while (k > 0) {int used = querySum(1, 0, n - 1, i, i);if (m - used >= k) {modify(1, 0, n - 1, i, used + k);break;}k -= m - used;modify(1, 0, n - 1, i, m);i++;}return true;}
};

代码详解

创建对象：初始化线段树用于存储可用状态和总状态。
modify方法：在指定位置更新，可在特定行添加已用座位，并更新线段树的相关节点。
gather方法：
- 使用queryMinRow找到满足条件的最小排。
- 如果找到，得到该排的当前已使用座位数，并在sumTree中进行更新。
scatter方法：
- 利用querySum计算余量并判断是否可行。
- 然后根据需要分配座位。
资源释放：在C语言版本中，通过bookMyShowFree方法进行分配的资源释放。