本文涉及知识点
线段树 最大值线段树
LeetCode2286. 以组为单位订音乐会的门票
一个音乐会总共有 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 * 104
1 <= m, k <= 109
0 <= maxRow <= n - 1
gather 和 scatter 总 调用次数不超过 5 * 104 次。
最大值线段树
第二种方式好解决：用向量记录各排剩余座位，并用start记录最小有剩余座位的排。本轮座位分配完毕后，start++。要判断能否满足，∑ x : 0 m a x R o w \sum_{x:0}^{maxRow}∑x:0maxRow 是否大于等于k。不能用前缀和，因为座位会变化，且不是一定从start开始减少，所以无法用前缀和。可用树状树状或线段树。
第一种方式，用最大值线段树。
先看[0,maxRow] 的最大值是否大于等于k，如果不是返回[]。
如果左半部分的最大值大于等于k，抛弃右半部分，不包括mid。
否则抛弃左半部分，包括mid。
故用左开右闭空间。
代码
核心代码
template<class ELE = int > class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize + 1) { } void Add(int index, ELE value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index & (-index); } } ELE Sum(int index) { index++; ELE ret = 0; while (index) { ret += m_vData[index]; index -= index & (-index); } return ret; } ELE Get(int index) { return Sum(index) - Sum(index - 1); } private: vector<ELE> m_vData; }; template<class TSave, class TRecord, TRecord RecordNull = 0> class CLineTree { public: CLineTree(int iEleSize) :m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vRecord(m_iEleSize * 4, RecordNull) { } void Update(int iLeftIndex, int iRightIndex, TRecord value) { Update(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1, value); } template<class TGet> void Query(const TGet& oGet, int iLeftIndex, int iRightIndex) { Query(oGet, 1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1); } private: virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) = 0; virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) = 0; virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) = 0; template<class TGet> void Query(const TGet& oGet, int iNode, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) { if ((iQueryLeft <= iSaveLeft) && (iQueryRight >= iSaveRight)) { oGet(m_vArr[iNode]); return; } Fresh(iNode, iSaveLeft, iSaveRight); const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (iMid >= iQueryLeft) { Query(oGet, iNode * 2, iSaveLeft, iMid, iQueryLeft, iQueryRight); } if (iMid + 1 <= iQueryRight) { Query(oGet, iNode * 2 + 1, iMid + 1, iSaveRight, iQueryLeft, iQueryRight); } } void Update(int iNode, int iSaveLeft, int iSaveRight, int iOpeLeft, int iOpeRight, TRecord value) { if (iNode >= m_vArr.size()) { return; } if ((iOpeLeft <= iSaveLeft) && (iOpeRight >= iSaveRight)) { OnUpdate(m_vArr[iNode], min(iSaveRight, iOpeRight) - max(iSaveLeft, iOpeLeft) + 1, value); OnUpdateRecord(m_vRecord[iNode], value); return; } Fresh(iNode, iSaveLeft, iSaveRight); const int iMid = iSaveLeft + (iSaveRight - iSaveLeft) / 2; if (iMid >= iOpeLeft) { Update(iNode * 2, iSaveLeft, iMid, iOpeLeft, iOpeRight, value); } if (iMid + 1 <= iOpeRight) { Update(iNode * 2 + 1, iMid + 1, iSaveRight, iOpeLeft, iOpeRight, value); } // 如果有后代，至少两个后代 OnUpdateParent(m_vArr[iNode], m_vArr[iNode * 2], m_vArr[iNode * 2 + 1]); } void Fresh(int iNode, int iDataLeft, int iDataRight) { if (RecordNull == m_vRecord[iNode]) { return; } const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2; Update(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vRecord[iNode]); Update(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vRecord[iNode]); m_vRecord[iNode] = RecordNull; } const int m_iEleSize; vector<TSave> m_vArr; vector<TRecord> m_vRecord; }; template<class TSave, class TRecord, TRecord RecordNull = 0> class CMaxLineTree : public CLineTree<TSave, TRecord, RecordNull> { using CLineTree< TSave, TRecord, RecordNull>::CLineTree; virtual void OnUpdateRecord(TRecord& old, const TRecord& newRecord) override { old = newRecord; } virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r) override { par = max(left, r); } virtual void OnUpdate(TSave& save, const int& len, const TRecord& iUpdate) override { save = iUpdate; } }; class BookMyShow { public: BookMyShow(int n, int m):m_lineTree(n), m_treeArr(n), m_iM(m){ for (int i = 0; i < n; i++) { m_treeArr.Add(i, m); } m_lineTree.Update(0, n - 1,m); } vector<int> gather(int k, int maxRow) { int iMax = 0; auto Get = [&iMax](int value) { iMax = max(iMax, value); }; m_lineTree.Query(Get, 0, maxRow); if (iMax < k) { return {}; } int left = -1, r = maxRow; while (r - left > 1) { const int mid = left + (r - left) / 2; iMax = 0; m_lineTree.Query(Get, 0, mid); if (iMax < k) { left = mid; } else { r = mid; } } const int cur = m_treeArr.Get(r); m_lineTree.Update(r, r, cur - k); m_treeArr.Add(r, -k); return { r,m_iM - cur }; } bool scatter(int k, int maxRow) { if (m_treeArr.Sum(maxRow) < k) { return false; } while (k > 0) { const int cur = (int)m_treeArr.Get(m_iStart); const int use = min(cur, k); k -= use; m_treeArr.Add(m_iStart, -use); m_lineTree.Update(m_iStart, m_iStart, cur - use); if (cur == use) { m_iStart++; } } return true; } CMaxLineTree<int,int,-1> m_lineTree; CTreeArr<long long> m_treeArr; int m_iStart = 0; const int m_iM; };
2023年3月
class CLineTree { public: CLineTree(int iArrSize) :m_iArrSize(iArrSize), m_vData(iArrSize * 4) {
} //iIndex 从0开始 void Modify( int iIndex, int iValue) { Modify(1, 1, m_iArrSize, iIndex + 1, iValue); } //iNeedQueryLeft iNeedQueryRight 从0开始 int Query(const int iNeedQueryLeft, const int iNeedQueryRight) { return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1); }
protected: int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight) { if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight)) { return m_vData[iTreeNodeIndex]; } const int iMid = (iRecordLeft + iRecordRight) / 2; int iRet = 0; if (iNeedQueryLeft <= iMid) { iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight); } if (iNeedQueryRight > iMid) { iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight)); } return iRet; } void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue) { if (iLeft == iRight) { m_vData[iTreeNodeIndex] = iValue; return; } const int iMid = (iLeft + iRight) / 2; if (iIndex <= iMid) { Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue); } else { Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue); } m_vData[iTreeNodeIndex] = max(m_vData[iTreeNodeIndex * 2], m_vData[iTreeNodeIndex * 2 + 1]); } const int m_iArrSize; std::vector m_vData; }; template class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize+1) {
} void Add(int index, T value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index&(-index); } } T Sum(int index) { index++; T ret = 0; while (index ) { ret += m_vData[index]; index -= index&(-index); } return ret; }
private: vector m_vData; }; class BookMyShow { public: BookMyShow(int n, int m) :m_r(n), m_c(m), m_maxLineTree(m_r), m_sumTreeArr(m_r) { m_vCanBuy.assign(m_r,m_c); for (int i = 0; i < m_r; i++) { m_maxLineTree.Modify(i, m_c); m_sumTreeArr.Add(i, m_c); } } vector gather(int k, int maxRow) { if (m_maxLineTree.Query(0, maxRow) < k) { return vector(); } int left = -1, right = maxRow ; while (right > left + 1) { int iMid = left + (right - left) / 2; if (m_maxLineTree.Query(0, iMid) < k ) { left = iMid; } else { right = iMid; } } vector vRet; vRet.push_back(right); vRet.push_back(m_c - m_vCanBuy[right]); Sell(right, k); Fresh(); return vRet; } bool scatter(int k, int maxRow) { if (m_sumTreeArr.Sum(maxRow) < k ) { return false; } for (int i = m_iPreSellOutRowNum; k > 0; i++) { const int iSell = min(k, m_vCanBuy[i]); Sell(i, iSell); k -= iSell; } Fresh(); return true; } void Sell(int r,int iNum) { m_vCanBuy[r] -= iNum; m_maxLineTree.Modify(r , m_vCanBuy[r]); m_sumTreeArr.Add(r,-iNum); } void Fresh() { while ((m_iPreSellOutRowNum < m_r) && (0 == m_vCanBuy[m_iPreSellOutRowNum])) { m_iPreSellOutRowNum++; } } const int m_r, m_c; vector m_vCanBuy;//各行剩余的票数，由于从左向右卖。所以一定剩下最右边的。 CLineTree m_maxLineTree;//记录各行，最大值 CTreeArr m_sumTreeArr;//方便求空闲座位之后 int m_iPreSellOutRowNum =0;//[0,m_iSellOutRow)行已经卖光 };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
