首页 > 其他分享 >(nice!!!)LeetCode 2286. 以组为单位订音乐会的门票(线段树)

(nice!!!)LeetCode 2286. 以组为单位订音乐会的门票(线段树)

时间:2024-09-28 21:19:28浏览次数:9  
标签:tmp 空位 int res 2286 maxRow 组为 long LeetCode

题目: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

相关文章

  • leetcode74 搜索二维矩阵
    leetcode74搜索二维矩阵思路可以使用二叉搜索,首先先看标准的闭区间二叉搜索代码publicintqSearch(int[]a,intl,intr,inttarget){intmid=(l+r)/2;if(l>r)returnl;//终止条件,区间为空if(a[mid]==target)returnmid;elseif(a[mid]<target)retur......
  • Leetcode 1235. 规划兼职工作
    1.题目基本信息1.1.题目描述你打算利用空闲时间来做兼职工作赚些零花钱。这里有n份兼职工作,每份工作预计从startTime[i]开始到endTime[i]结束,报酬为profit[i]。给你一份兼职工作表,包含开始时间startTime,结束时间endTime和预计报酬profit三个数组,请你计算并返回可......
  • Leetcode面试经典150题-64.最小路径和
    给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。示例1:输入:grid=[[1,3,1],[1,5,1],[4,2,1]]输出:7解释:因为路径1→3→1→1→1的总和最小。示例2:输入:grid=[[1......
  • LeetCode--Dota2 参议院(day 2)
     今天给大家带来LeetCode中的一道算法题:参议院问题,忘记具体内容的朋友可以观看下图: 根据题意,我们可以清楚的认识到获胜条件:那就是字符串中仅包含D或R。 我们先以RDRDD为例进行说明: 字符串中的第一个R行使权力,淘汰D阵营中的某一位,我们可以看见字符串中有三个D,那么该......
  • leetCode--爬楼梯(记录做题过程加深印象)
    首先最广泛的方法为递归,直接上代码:intclimbStairs(intn){if(n==1){return1;}if(n==2){return2;}if(flag[n])returnflag[n];returnflag[n]=climbStairs(n-1)+climbStair......
  • 【算法题】72. 编辑距离-力扣(LeetCode)
    【算法题】72.编辑距离-力扣(LeetCode)1.题目下方是力扣官方题目的地址72.编辑距离给你两个单词word1和word2,请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作:插入一个字符删除一个字符替换一个字符示例1:输入:word1="ho......
  • 875. 爱吃香蕉的珂珂(leetcode)
    https://leetcode.cn/problems/koko-eating-bananas/description/二段性:速度有得完和不吃完两个段关键点是编写check函数,比较繁杂classSolution{publicintminEatingSpeed(int[]piles,inth){intsum=0;intmax=0;for(inti=0;i<piles.......
  • Leetcode 154. 寻找旋转排序数组中的最小值 II
    1.题目基本信息1.1.题目描述已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如,原数组nums=[0,1,4,4,5,6,7]在变化后可能得到:若旋转4次,则可以得到[4,5,6,7,0,1,4]若旋转7次,则可以得到[0,1,4,4,5,6,7]注意,数组[a[0],a[1],a[2],......
  • 【LeetCode Hot 100】21. 合并两个有序链表
    题目描述最简单粗暴的想法是将两个链表的所有元素拿出来放在一个数组中,再将此数组排序,最后生成一个新链表并返回。由于给出的参数本身就是两个排好序的链表,可以进行一次遍历,就能保证元素仍然是有序的:每次比较当前指针指向的两个元素的大小,较小的拿出来作为当前元素并将指针向前移......
  • LeetCode刷题日记之二叉树(二)
    目录前言左叶子之和找树左小角的值总结前言经过数模比赛的四天忙碌后博主继续开始LeetCode学习了,给大家分享学习心路的同时也是在不断勉励自己每天把自己的学的东西去进行一个产出记录,不足的地方欢迎大家批评指正,一起加油吧朋友们!......