【算法实战】每日一题：17.1 订单处理问题（差分思想，二分搜索）

题目

一个会议中心的场地预订系统。在接下来的 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 i=1;i<=num;i++){sub[s[i]] +=d[i];sub[t[i]+1]-=d[i];}// 然后这样的话，我们就得到了一个。一维的数组，里面存储着。订单的。每一天的订单的数量。for (int i=1;i<=n;i++){// 然后这里注意，因为这里是对区间进行处理，然后每一个订单里面它都是几天到几天啊，它需要增加多少订单数啊，所以它很明显就是天然就是一个差分数组的形式啊。假如说没有订单的话，那每天都是需求数都是零。啊，但是这里的话给了每天的订单，那么这里就直接使用差分数组的方式来进行处理。这里的// 这里的查封的意思实际上可以理解为前一天河道后一天的需求X啊，如果说订单是零的话，那么需求差就是全部是零啊，也就是上面这里写的这个啊，刚开始初始化的时候都设置为零，然后开始往里面加订单啊，哪一天到哪一天里面啊，需要增加多少的数量啊，所以很明显就天然。是一个查封数组的形式，然后上面由于我们这里是，呃，天然是一个茶壶数组的形式，那么我们使用查封数组拉伸区间的方法去对它进行相加。然后这里的话我们就需要得到他的原始的数据啊。如果说。我的需求数啊，是大于。我目前拥有的这个房间的数量那么很满，很显然就是满足条件了啊我就把return true。// 这里还有一点注意的就是它实际上是从一开始的。所以啊，这里就考虑到初始化的问题啊，我就不用初始化了然后每次第一列都是默认是零，然后我从一开始。need[i] = need[i-1] + sub[i];if (need[i]>r[i])return true;}return false;
}//主函数二分搜索// 那么如果说有一些订单是无法满足的。那么我为了提高效率啊，我就可以啊。每次只进行1/2的查找啊，就是找到这个最关键的时间点。呃，换句话说，这里实际上是找到那个问题，订单啊，最快的方法，那么我们可以很简单地用一个二分查找方。while (le<=ri){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 = mid+1; } 

上面的代码为截取最关键的一部分分析，代码思路来源于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