題目描述

在大學期間，經常需要租借教室。大到院系舉辦活動，小到學習小組自習討論，都需要向學校申請借教室。教室的大小功能不同，借教室人的身份不同，借教室的手續也不一樣。

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

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

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

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

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

輸入輸出格式

輸入格式：

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

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

接下來有m行，每行包含三個正整數dj?,sj?,tj?，表示租借的數量，租借開始、結束分別在第幾天。

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

輸出格式：

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

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

輸入輸出樣例

輸入樣例#1：

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

輸出樣例#1：

-1?
2

思路：

首先，判斷當前狀態所有任務是否能夠滿足每天借教室的量在允許范圍內，然后用差分數組記錄當前狀態在每天對教室的總需求與前一天的差值，那么很容易求得每一天的實際值：n[i]=sum(f[i])

然后與當天允許的教室數量進行比較，若大于提供量，則不可借出，之后檢測 m 種任務能否同時執行，若可行則直接輸出0，若不可行就二分答案，直到該狀態所有任務都可滿足

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define PI acos(-1.0) #define E 1e-9 #define INF 0x3f3f3f3f #define LL long long const int MOD=1000000007; const int N=1000000+5; const int dx[]= {-1,1,0,0}; const int dy[]= {0,0,-1,1}; using namespace std;int n,m; struct Node{int num;//要租借的數量int start,endd;//租借開始與結束時間 }a[N]; int f[N]; int admit[N];//每天允許借出數量 bool judge(int x){//判斷m個訂單能否同時執行memset(f,0,sizeof(f));for(int i=1;i<=x;i++){//差分數組f[a[i].start]+=a[i].num;f[a[i].endd+1]-=a[i].num;}int sum=0;for(int i=1;i<=n;i++){//查詢第i天的值sum+=f[i];if(sum>admit[i])return false;}return true; } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&admit[i]);for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].num,&a[i].start,&a[i].endd);if(judge(m))printf("0\n");else{//二分答案int left=1,right=m;while(left<right){int mid=(left+right)/2;if(judge(mid)) left=mid+1;else right=mid;}printf("-1\n%d\n",left);}return 0; }

?

總結

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

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