题目:2286. 以组为单位订音乐会的门票
思路:线段树做法。(线段树)acwing 1265. 数星星
class BookMyShow {
public:
//结构体
typedef struct Node{
int mn=0; // 最小空位编号
long long sum=0; //非空位置之和
}node;
//n,m
int N,M;
//线段树
vector<node> v;
//用于记录调用方法modify()时,当前最小空位的编号
int tmp=0;
//更新操作
void push_up(int u){
v[u].mn=min(v[u<<1].mn,v[u<<1|1].mn);
v[u].sum=v[u<<1].sum+v[u<<1|1].sum;
}
//找到最前面的“最小空位的编号”小于k的排数
int findd(int u,int l,int r,int k){
//只剩当前排
if(l==r){
//符合要求,返回排数
if(v[u].mn<=k) return l;
else return -1;
}
//如果当前区间的“最小空位的编号”<=k时
if(v[u].mn<=k){
//进行二分,因为要找到最前面的
int mid=(l+r)/2;
//如果左边的“最小空位的编号”符合要求
if(v[u<<1].mn<=k) return findd(u<<1,l,mid,k);
else return findd(u<<1|1,mid+1,r,k);
}
else return -1;
}
//修改区间[L,R]的位置值,这里实际调研的时候,L==R
void modify(int u,int l,int r,int L,int R,int k){
//在此区间
if(L<=l&&r<=R){
v[u].mn+=k;
//tmp记录当前最小空位的编号
tmp=v[u].sum;
v[u].sum+=k;
return ;
}
int mid=(l+r)/2;
if(L<=mid) modify(u<<1,l,mid,L,R,k);
if(R>mid) modify(u<<1|1,mid+1,r,L,R,k);
//更新操作
push_up(u);
}
//查询区间[L,R]之间已经使用的座位数量
long long query(int u,int l,int r,int L,int R){
if(L<=l&&r<=R) return v[u].sum;
int mid=(l+r)/2;
long long res=0;
if(L<=mid) res+=query(u<<1,l,mid,L,R);
if(mid<R)res+=query(u<<1|1,mid+1,r,L,R);
return res;
}
BookMyShow(int n, int m) {
N=n;
M=m;
//数组构建线段树
v=vector<node>(n<<2);
}
vector<int> gather(int k, int maxRow) {
vector<int> res;
//找到最前面的“最小空位的编号”小于M-k的排数
int r=findd(1,0,N-1,M-k);
//没有就直接返回
if(r<0||r>maxRow) return res;
//记录排数
res.push_back(r);
//进行修改
modify(1,0,N-1,r,r,k);
//modify时会记录“最小空位的编号”
res.push_back(tmp);
return res;
}
bool scatter(int k, int maxRow) {
//看区间[0,maxRow]已经使用过的座位数量
long long sum=query(1,0,N-1,0,maxRow);
//如果剩余座位不够
if(sum+k>(long long)(1+maxRow)*M) return false;
//循环
while(k){
//找到最前面的“最小空位的编号”小于M-1的排数
int r=findd(1,0,N-1,M-1);
//获得r排已经使用过的座位数量
int tmp=query(1,0,N-1,r,r);
//最多能使用的座位
int res=min(M-tmp,k);
//进行更新
modify(1,0,N-1,r,r,res);
k-=res;
}
return true;
}
};
/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow* obj = new BookMyShow(n, m);
* vector<int> param_1 = obj->gather(k,maxRow);
* bool param_2 = obj->scatter(k,maxRow);
*/
标签:tmp,空位,int,res,2286,maxRow,组为,long,LeetCode
From: https://blog.csdn.net/weixin_46028214/article/details/142621877