898
房間安排
房間安排
時間限製：3000 ms | 內存限製：65535 KB
難度：1
- 描述
-
2010年上海世界博覽會(Expo2010),是第41屆世界博覽會。於2010年5月1日至10月31日期間，在中國上海市舉行。本次世博會也是由中國舉辦的首屆世界博覽會。上海世博會以“城市，讓生活更美好”(Better City,Better Life)為主題，將充分探索21世紀城市生活。
這次世博會總投資達450億人民幣，創造了世界博覽會史上的最大規模記錄。吸引200個國家和國際組織參展。預計有7000萬人次的參觀者。
為了更好地接待在這期間來自世界各地的參觀者，如何合理安排各賓館的住房問題提到了日程。組委會已接到了大量的客戶住宿定單，每張定單的內容包括要住宿的房間數，開始住宿時間和要住的天數。為了便於整個城市各賓館的管理，組委會希望對這些定單進行安排，目的是用盡可能少的房間來滿足這些定單，以便空出更多的房間用於安排流動遊客。
組委會請求DR.Kong來完成這個任務，對這些定單進行合理安排，使得滿足這些定單要求的房間數最少。
假設：某個定單上的遊客一旦被安排到某房間，在他預定住宿的期間內是不換房間的。為了簡化描述，定單上的開始住宿時間為距離現在的第幾天。例如，定單為（10，30，5）表示遊客要求使用10個房間，第30天開始連住5天。
- 輸入
- 第一行：T 表示有T組測試數據
每組測試數據第一行：N 表示定單數
每組測試數據接下來有N行，每行有三個整數 A B C 表示房間數，開始住宿時間和天數
1<=T<=100
1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10 - 輸出
- 輸出一個整數，為滿足所有定單要求的最少房間數。
- 樣例輸入
-
1 3 3 10 4 4 9 3 3 12 6
- 樣例輸出
-
7
01.#include <iostream>
02.#include <cstring>
03.using
namespace std;
04.
05.int
main()
06.{
07.int
testNum;
08.int
r[200];
09.
10.cin >> testNum;
11.while
(testNum--)
12.{
13.memset(r, 0,
sizeof(r));
14.int
orderNum;//定單數
15.cin >> orderNum;
16.
17.int
a, b, c;
18.while
(orderNum--)
19.{
20.cin >> a >> b >> c;
21.for
(int
i = b; i < b+c; i++)
22.{
23.r[i] += a;
24.}
25.}
26.for
(int
i = 1; i < 200; i++)
27.{
28.if
(r[0] < r[i])
29.r[0] = r[i];
30.}
31.cout << r[0] << endl;
32.
33.}
34.return
0;
35.}
最後更新：2017-04-03 05:40:24