NOIP提高組2012 洛谷P1083 借教室 二分答案+差分 C++

題目鏈接：https://www.luogu.com.cn/problem/P1083

題目大意：現有n天，每天有 r i r_i ri?的空教室可供租借，當前有m個具有先后次序的訂單，每個訂單的要求是在第 l i l_i li?天到第 r i r_i ri?天占用 d i d_i di?間教室，要求編程，從先到后處理這些訂單，倘若到了第 j j j個訂單不能被滿足，則輸出-1換行后，輸出該訂單號，倘若所有都可以同時滿足，則輸出0，結束程式，

資料范圍如下圖所示：

我們從100%的資料可以看出，這題標準思路的時間復雜度應該是 O ( n l o g n ) O(nlogn) O(nlogn)，并且從答案的單調性可以得知應該是二分做法，對此我們暫時跳過，先分析樸素做法，

樸素做法：預期得分 30~40分

我們用模擬的思路，這個思路應該很容易想到，首先用陣列 e m p t y _ r o o m [ i ] empty\_room[i] empty_room[i]記錄每天的空教室，用 l e f t [ i ] left[i] left[i]記錄每個訂單的左邊界，用 r i g h t [ i ] right[i] right[i]記錄每個訂單的右邊界，最后用 v a l u e [ i ] value[i] value[i]記錄每個訂單租借的數量，

我們依次處理每個訂單，處理的方法是在 e m p t y _ r o o m [ i ] empty\_room[i] empty_room[i]陣列上，對于每個訂單的左邊界到右邊界，減去租借教室的數量，倘若處理到第 j j j個訂單時，出現了 e m p t y _ r o o m [ i ] empty\_room[i] empty_room[i]陣列的第 i i i個元素是負數的情況，就說明第 i i i天教室不夠用，此時可以輸出答案，

倘若m個訂單全部處理完畢，陣列上沒有負數的情況，說明每天的空教室都夠用，此時輸出答案0即可，

分析一下預期得分，這個做法最壞情況的時間復雜度是O(m*n)，其實還說得過去，30分穩穩拿，對于70%的資料范圍靠人品和卡常有概率偷來幾個點，不過兩個點不能再多了，

二分答案+差分做法：預期得分 100分

從資料范圍上看，我們可以從二分的方向去考慮，二分的前提條件是答案具有單調性，那么我們需要先要確定這個前提條件，在處理訂單的流程中，我們每一天的空教室數量只能減少，不能增多，這說明處理到某個訂單時某一天的教室不夠用了，之后再處理訂單只會導致教室更加不夠用，雖然推理不嚴謹，但是這個單調性還是可以通過邏輯想清楚的，

因此我們可以確定基本的二分答案思路，確定二分的左邊界( b e g i n begin begin)為 1 1 1，右邊界( e n d end end)為 m m m， m i d = ( 1 + m ) / 2 mid=(1+m)/2 mid=(1+m)/2，假設答案是 m i d mid mid，計算在該答案下教室是否夠用，若夠用則做出調整 b e g i n = m i d begin=mid begin=mid，若不夠用則做出另一種調整 e n d = m i d end=mid end=mid，這里二分的復雜度是 O ( log ? n ) O({\log}n) O(logn)，現在我們需要考慮如何在 O ( n ) O(n) O(n)的復雜度，完成一次答案檢驗的操作，

這個時候需要用到差分的技巧，我們就該題進行一個分析：我們一共有m個訂單，這m個訂單的操作都是對于一個區間進行增減，而當前復雜度希望的是我們僅遍歷一次陣列的每個元素就可以完成這m個區間的增減，這意味著我們可以用"打標記"的方法來完成這一目的，我們首先設立一個陣列 d i f f [ u ] diff[u] diff[u]作為我們的標記陣列，區間的左邊界 l e f t [ i ] left[i] left[i]我們把它定義為“增標記”，代表一個區間的開始，操作是 d i f f [ l e f t [ u ] ] + v a l u e [ u ] diff[left[u]]+value[u] diff[left[u]]+value[u]；區間的右邊界 r i g h t [ i ] right[i] right[i]，我們把它定義為“減標記”，操作是 d i f f [ r i g h t [ u ] ] ? v a l u e [ u ] diff[right[u]]-value[u] diff[right[u]]?value[u]代表的一個區間的結束，并且每個點上的值都是可以疊加的，當我們對空教室陣列進行遍歷時，這個標記陣列就記載了所有單個區間修改操作疊加在一起的總操作，在對 e m p t y _ r o o m [ i ] empty\_room[i] empty_room[i]陣列進行遍歷時，遍歷到某一點 i i i時， e m p t y r o o m [ i ? 1 ] + d i f f [ i ] empty_room[i-1]+diff[i] emptyr?oom[i?1]+diff[i]即為 i i i點剩下的空教室數量，這樣我們通過標記陣列 d i f f [ u ] diff[u] diff[u]，可以完成所有區間更改操作，時間復雜度是 O ( n + m ) O(n+m) O(n+m)，也就是 O ( n ) O(n) O(n)，若空教室陣列中有元素為負數則到當前訂單時不可行，若空教室陣列全為正數，則當前訂單及之前的訂單都可行，（標記陣列就是差分陣列）

這樣我們的總復雜度就是 O ( n l o g n ) O(nlogn) O(nlogn)，可行，下面展示代碼，

#include<bits/stdc++.h>
using namespace std;
int a[1000011],d[1000011],l[1000011],r[1000011];
long long modify[1000011];
int n,m;
bool pd(int x)
{
	memset(modify,0,sizeof(modify));//清空差分陣列modify
	for(int i=1;i<=x;i++)//將每個區間的更改記錄在差分陣列上
	{
		modify[l[i]]+=d[i];
		modify[r[i]+1]-=d[i];
	}
	long long p=0;//為降低時間復雜度，我們不另起一個陣列，而是通過p來記錄共有x個訂單時，
	for(int i=1;i<=n;i++)//對于某一天教室的需求量，用需求量與現有量進行對比，
	{
		p+=modify[i];
		if(p>a[i]) return 0;
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>d[i]>>l[i]>>r[i];
	}
	if(pd(m))
	{
		cout<<0;
		return 0;
	}
	else cout<<-1<<endl;
	int begin=1,end=m;
	while(begin<end)
	{ 
		int mid=(begin+end)/2;
		if(pd(mid))
		{
			begin=mid+1;
		}
		else
		{
			end=mid; 
		}
	}
	cout<<begin;
 } 

有疏漏和講解不清的地方請私信留言，祝你新的一天RP++，