https://www.luogu.org/problem/P1083
題目描述
在大學期間，經常需要租借教室。大到院系舉辦活動，小到學習小組自習討論，都需要向學校申請借教室。教室的大小功能不同，借教室人的身份不同，借教室的手續也不一樣。

面對海量租借教室的信息，我們自然希望編程解決這個問題。

我們需要處理接下來n天的借教室信息，其中第ii天學校有ri
? 個教室可供租借。共有m份訂單，每份訂單用三個正整數描述，分別為d j? ,s j,t j ，表示某租借者需要從第s j天到第t j天租借教室（包括第s j 天和第t j 天），每天需要租借d j個教室。

我們假定，租借者對教室的大小、地點沒有要求。即對于每份訂單，我們只需要每天提供d j 個教室，而它們具體是哪些教室，每天是否是相同的教室則不用考慮。

借教室的原則是先到先得，也就是說我們要按照訂單的先后順序依次為每份訂單分配教室。如果在分配的過程中遇到一份訂單無法完全滿足，則需要停止教室的分配，通知當前申請人修改訂單。這里的無法滿足指從第s j 天到第t j天中有至少一天剩余的教室數量不足d j個。

現在我們需要知道，是否會有訂單無法完全滿足。如果有，需要通知哪一個申請人修改訂單。

輸入格式
第一行包含兩個正整數n,m，表示天數和訂單的數量。

第二行包含n個正整數，其中第ii個數為r i
? ，表示第ii天可用于租借的教室數量。

接下來有mm行，每行包含三個正整數d j,s j,t j ，表示租借的數量，租借開始、結束分別在第幾天。

每行相鄰的兩個數之間均用一個空格隔開。天數與訂單均用從11開始的整數編號。

輸出格式
如果所有訂單均可滿足，則輸出只有一行，包含一個整數 0。否則（訂單無法完全滿足）

輸出兩行，第一行輸出一個負整數-1，第二行輸出需要修改訂單的申請人編號。

輸入輸出樣例
輸入 #1 復制

4 3 2 5 4 3 2 1 3 3 2 4 4 2 4

輸出 #1 復制

-1 2

說明/提示
【輸入輸出樣例說明】

第 1 1份訂單滿足后，4天剩余的教室數分別為0,3,2,3。第 2 份訂單要求第 2天到第 4 天每天提供 3個教室，而第 3 天剩余的教室數為 2，因此無法滿足。分配停止，通知第2 個申請人修改訂單。

【數據范圍】

對于10%的數據，有1≤n,m≤10；

對于30%的數據，有1≤n,m≤1000；

對于 70%的數據，有1 ≤ n,m ≤ 10^5
；

對于 100%的數據，有1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n1≤n,m≤1e6

NOIP 2012 提高組 第二天 第二題
AC_code:
/*
首先這個涉及到區間的修改，區間修改快速維護除了線段樹，樹狀數組啥的，
那就是差分法啦~~
簡單介紹一下差分法：
一個序列：
1 4 5 3 7
差分序列：
1 3 1 -2 4
（a[i] - a[i-1]的值，第一個與虛擬一個0（a[0] = 0）進行求差）
根據差分序列前綴和可以得到原序列的值：
0+1 = 1；
1 + 3 = 4
4 + 1 = 5
5 -2 = 3
3 +4 = 7
對于區間修改[l,r]，對這個區間上的值加上c,
只需要在對應的差分序列上，
l位置+c
r+1位置-c
即可實現[l.r]區值的修改
比如對上面序列[2,3]這個區間上的值+2
差分序列位置：
l ： 3+2 = 5；

r+1 ：4-2 = 2；

此時差分序列變為：
1 5 1 -2 2
根據前綴和轉換為需要的序列：
1 6 7 5 7（原來是1 4 5 3 7，對[2,3],+2）
此時 是不是神速的修改了區間吶~，神奇的東西！！！

然后本題要找第一個不滿足的位置。
由于申請人的編號是有序的，
so可以對申請人數據
用二分來找第一個不滿足的位置（即編號）
*/

#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6+5; int a[MAXN]; int b[MAXN]; int v[MAXN]; int n,m; struct Node {int c;int s,e; } node[MAXN]; bool check(int mid) {for(int i = 1; i <= n; i++){b[i] = a[i];}for(int i = 1; i <= mid; i++){int x = node[i].s;int y = node[i].e;b[x] -= node[i].c;b[y+1] += node[i].c;}int sum = 0;for(int i = 1; i <= n; i++){sum += b[i];/*如果此時差分序列前綴和（對應某一天的教室余量）都小于0，那肯定是不滿足的一個位置，即此時可以考慮前移，因為要找第一個不滿足*/if(sum < 0)return true;}return false; } int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;memset(a,0,sizeof(a));for(int i = 1; i <= n; i++){cin>>a[i];}for(int i = n; i > 0; i--){a[i] -= a[i-1];}for(int i = 1; i <= m; i++){cin>>node[i].c>>node[i].s>>node[i].e;}int l = 1,r = m;int res = -1;while(l <= r){int mid = (l+r)>>1;if(check(mid)){res = mid;r = mid - 1;}else{l = mid + 1;}}if(res != -1)cout<<"-1\n"<<res<<endl;elsecout<<0<<endl;return 0; }

總結

以上是生活随笔為你收集整理的P1083 借教室（差分+二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。