【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票-阿里云开发者社区

本文涉及知识点

线段树最大值线段树

二分查找算法合集

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 * 10⁴

1 <= m, k <= 10⁹

0 <= maxRow <= n - 1

gather 和 scatter 总调用次数不超过 5 * 10⁴ 次。

最大值线段树

第二种方式好解决：用向量记录各排剩余座位，并用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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。

【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票

本文涉及知识点

LeetCode2286. 以组为单位订音乐会的门票

最大值线段树

代码

核心代码

2023年3月

扩展阅读

视频课程

相关下载

测试环境

热门文章

最新文章

相关电子书