a0000网站建设,做哪个网站的直播好,建设一个网站大概需要多久,wordpress修改文章链接地址题目
一个会议中心的场地预订系统。在接下来的 n 天里#xff0c;会议中心有一定数量的会议室可供租用。共有 m 份预订请求#xff0c;每份请求描述为 (d_i, a_i, b_i)#xff0c;表示需要从第 a_i 天到第 b_i 天使用会议室#xff08;包括第 a_i 天和第 b_i 天#xff0…题目
一个会议中心的场地预订系统。在接下来的 n 天里会议中心有一定数量的会议室可供租用。共有 m 份预订请求每份请求描述为 (d_i, a_i, b_i)表示需要从第 a_i 天到第 b_i 天使用会议室包括第 a_i 天和第 b_i 天每天需要使用 d_i 个会议室。预订按照提交时间顺序处理如果某个请求的需求超出了会议中心剩余的会议室数量那么需要暂停处理流程通知当前申请者调整他们的请求。工作人员需要知道是否所有的请求都能被完全满足如果不能还需要知道需要调整的是哪一份请求。
初步代码
def process_orders(n, m, room_availability, orders):# 创建一个变量的副本。available_rooms room_availability.copy()for order in orders:# 这里的话就是根据我当前拿到的订单然后去。房间里面对应的去查看。d, start_day, end_day orderfor day in range(start_day, end_day 1):# 这里的话就是我当前的订单是。是不是可以剩余啊如果说这里是。我当前的房间数量不能满足你的订单数啊那我就return一个负一。 # 那么我这里根据要求第一个行返回一个负一啊。第二行我返回当前的一个索引啊也就是呃我当前是因为拿到了一行嘛我当前拿到的是一行我当前拿到的一行的话orders去调用这个index的方法。那就是看我当前的这个东西在你这里面的索引是多少啊又因为Python是从零开始的所以得加一。if available_rooms[day] d:return -1, orders.index(order) 1# 那么如果说我当前的房间是满足你的这个订单的话那么我就减等于一啊然后不断地过去。available_rooms[day] - dreturn 0 if __name__ __main__:# n表示总共N个天数总共有三个订单。n, m map(int, input().split())# 这里输入每天房间可以用的情况。room_availability list(map(int, input().split()))orders []for _ in range(m):orders.append(list(map(int, input().split())))# 然后这边返回以后的话我们再对结果进行判断啊。这里是按照他的要求如果是零的话返回给零如果有不满足订单返回一个复议以及索引。 result, order_to_modify process_orders(n, m, room_availability, orders)if result 0:print(0)else:print(-1)print(order_to_modify)
很显然这样的思路有很大的优化的空间。这里我们只是单纯地对每一步进行操作。那么换1种思路。比如使用差分数组的方法可以优化代码 // 这个函数实际上处理的是传入的这个NUM5之前的。进行检查。
bool check(int num){// 这里设置为零就是单纯做一个初始化然后下面用差分数组的方法啊给它每一个区域的订单数都会拉伸或者啊做拉伸起来。for (int i1;inum;i){sub[s[i]] d[i];sub[t[i]1]-d[i];}// 然后这样的话我们就得到了一个。一维的数组里面存储着。订单的。每一天的订单的数量。for (int i1;in;i){// 然后这里注意因为这里是对区间进行处理然后每一个订单里面它都是几天到几天啊它需要增加多少订单数啊所以它很明显就是天然就是一个差分数组的形式啊。假如说没有订单的话那每天都是需求数都是零。啊但是这里的话给了每天的订单那么这里就直接使用差分数组的方式来进行处理。这里的// 这里的查封的意思实际上可以理解为前一天河道后一天的需求X啊如果说订单是零的话那么需求差就是全部是零啊也就是上面这里写的这个啊刚开始初始化的时候都设置为零然后开始往里面加订单啊哪一天到哪一天里面啊需要增加多少的数量啊所以很明显就天然。是一个查封数组的形式然后上面由于我们这里是呃天然是一个茶壶数组的形式那么我们使用查封数组拉伸区间的方法去对它进行相加。然后这里的话我们就需要得到他的原始的数据啊。如果说。我的需求数啊是大于。我目前拥有的这个房间的数量那么很满很显然就是满足条件了啊我就把return true。// 这里还有一点注意的就是它实际上是从一开始的。所以啊这里就考虑到初始化的问题啊我就不用初始化了然后每次第一列都是默认是零然后我从一开始。need[i] need[i-1] sub[i];if (need[i]r[i])return true;}return false;
}//主函数二分搜索// 那么如果说有一些订单是无法满足的。那么我为了提高效率啊我就可以啊。每次只进行1/2的查找啊就是找到这个最关键的时间点。呃换句话说这里实际上是找到那个问题订单啊最快的方法那么我们可以很简单地用一个二分查找方。while (leri){mid le (ri-le)/2;// 这里就是如果我发现了在左半部分是这个问题点那么我就去左半部分找否则的话我就去用半部分找。// ans的作用是记录当前找到最大的订单数。// 这里特别要注意啊就是二分查找它的前提必须是输入的数据是有序的才能用二分查找这里因为提供给的他的数据都是有序的所以我们可以直接用。if(check(mid)){ri mid-1;// 并且由于是有序的那么我在左半部分它的最大值就是 中间最中间的那个。// 这里注意啊为什么左半边有需要去Kan S复制啊右半部分没有啊首先这里的mid就是索引我们看到上面Le和ri呃是一和M这里是长度。那么这里给他整除了以后就是它中间的那个数啊也就是表示的是索引然后因为我们是从前往后逐个的去找。啊这么那么在进行二分查找的过程中我们想过啊如果是我们在左半部分找到了啊。那我们就压缩这个空间啊啊按从右往左然后逐个的去压缩空间啊。如果说你在右边找到呢那其实也一样啊右边找到了以后你到最后肯定是呃把这个空间给逐步缩小的。// 这里的文化an S放在这里主要是从逻辑上来讲啊因为我们的check函数是啊以当前位置为准然后向前去找这个问题点啊如果说。呃这个check函数它是为true的话那么表示问题点在当前的维乾那么就是以made made以前啊那么made也是1种可能并且是1种最大的可能性啊。所以说这里主要是因为逻辑原因啊并不是别的什么原因。ans mid; }else{le mid1; }
上面的代码为截取最关键的一部分分析代码思路来源于bilbli轩哥码题注释为随笔只说明大概思路
这里的订单处理问题很显然天然的用到了差分的思想。
N 10**6def check(num, n, r, d, s, t):sub [0] * (N 1)for i in range(1, num 1):sub[s[i]] d[i]sub[t[i] 1] - d[i]need [0] * (N 1)for i in range(1, n 1):need[i] need[i - 1] sub[i]if need[i] r[i]:return Truereturn Falsedef main():n, m map(int, input().split())r [0] * (N 1)d [0] * (N 1)s [0] * (N 1)t [0] * (N 1)temp_r list(map(int, input().split()))for i in range(1, n 1):r[i] temp_r[i - 1]for i in range(m): temp list(map(int, input().split()))d[i], s[i], t[i] temple, ri 1, mif not check(m, n, r, d, s, t):print(0)returnwhile le ri:mid le (ri - le) // 2if check(mid, n, r, d, s, t):ri mid - 1ans midelse:le mid 1print(-1)print(ans)if __name__ __main__:main()
END
