房間安排（nyoj168）

描寫

2010年上海世界展覽會(Expo2010),是第41屆世界展覽會。于2010年5月1日至10月31日期間，在中國上海市舉行。本次世博會也是由中國舉行的首屆世界展覽會。上海世博會以“城市，讓生活更美好”(Better City,Better Life)為主題，將充分探索21世紀城市生活。

這次世博會總投資達450億人民幣，創造了世界展覽會史上的最大范圍記錄。吸引200個國家和國際組織參展。預計有7000萬人次的參觀者。

為了更好地接待在這期間來自世界各地的參觀者，如何公道安排各賓館的住房問題提到了日程。組委會已接到了大量的客戶住宿訂單，每張訂單的內容包括要住宿的房間數，開始住宿時間和要住的天數。為了便于全部城市各賓館的管理，組委會希望對這些訂單進行安排，目的是用盡量少的房間來滿足這些訂單，以便空出更多的房間用于安排活動游客。

組委會要求DR.Kong來完成這個任務，對這些訂單進行公道安排，使得滿足這些訂單要求的房間數最少。

假定：某個訂單上的游客1旦被安排到某房間，在他預定住宿的期間內是不換房間的。為了簡化描寫，訂單上的開始住宿時間為距離現在的第幾天。例如，訂單為（10，30，5）表示游客要求使用10個房間，第30天開始連住5天。

輸入

第1行：T 表示有T組測試數據
每組測試數據第1行：N 表示訂單數
每組測試數據接下來有N行，每行有3個整數 A B C 表示房間數，開始住宿時間和天數
1<=T<=100
1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10

輸出

輸出1個整數，為滿足所有訂單要求的最少房間數。

樣例輸入

1 3 3 10 4 4 9 3 3 12 6

樣例輸出

7

來源

第3屆河南省程序設計大賽

上傳者

張云聰

       開1個數組，表示房間數，把每個定單的開始時間到結束時間，每一個
數組加上需要的房間數，如果多個定單時間有重復，則房間數會累加，從而
得到各個時間段所用的房間數，找出最大值即為需要的最少的房間數。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int s[10005]; int main() { int i,j,n,test,ans,a,b,c; scanf("%d",&test); while(test--) { memset(s,0,sizeof(s)); scanf("%d",&n); for(i=0,ans=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); for(j=b;j<b+c;j++) { s[j]+=a; ans=max(s[j],ans); } } printf("%d ",ans); } return 0; }

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈