房間安排（nyoj168）

描寫(xiě)

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

這次世博會(huì)總投資達(dá)450億人民幣，創(chuàng)造了世界展覽會(huì)史上的最大范圍記錄。吸引200個(gè)國(guó)家和國(guó)際組織參展。預(yù)計(jì)有7000萬(wàn)人次的參觀者。

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

組委會(huì)要求DR.Kong來(lái)完成這個(gè)任務(wù)，對(duì)這些訂單進(jìn)行公道安排，使得滿足這些訂單要求的房間數(shù)最少。

假定：某個(gè)訂單上的游客1旦被安排到某房間，在他預(yù)定住宿的期間內(nèi)是不換房間的。為了簡(jiǎn)化描寫(xiě)，訂單上的開(kāi)始住宿時(shí)間為距離現(xiàn)在的第幾天。例如，訂單為（10，30，5）表示游客要求使用10個(gè)房間，第30天開(kāi)始連住5天。

輸入

第1行：T 表示有T組測(cè)試數(shù)據(jù)
每組測(cè)試數(shù)據(jù)第1行：N 表示訂單數(shù)
每組測(cè)試數(shù)據(jù)接下來(lái)有N行，每行有3個(gè)整數(shù) A B C 表示房間數(shù)，開(kāi)始住宿時(shí)間和天數(shù)
1<=T<=100
1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10

輸出

輸出1個(gè)整數(shù)，為滿足所有訂單要求的最少房間數(shù)。

樣例輸入

1 3 3 10 4 4 9 3 3 12 6

樣例輸出

7

來(lái)源

第3屆河南省程序設(shè)計(jì)大賽

上傳者

張?jiān)坡?/p>

       開(kāi)1個(gè)數(shù)組，表示房間數(shù)，把每個(gè)定單的開(kāi)始時(shí)間到結(jié)束時(shí)間，每一個(gè)
數(shù)組加上需要的房間數(shù)，如果多個(gè)定單時(shí)間有重復(fù)，則房間數(shù)會(huì)累加，從而
得到各個(gè)時(shí)間段所用的房間數(shù)，找出最大值即為需要的最少的房間數(shù)。

#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; }

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)