【题目描述】:

2180年奥运会竞技类分会场,将在XX市举行。会场自然是政府的事情,我们就别操心了。艾瑞克却被兴奋而苦恼的情绪折磨着,他的宾馆是XX市最好的宾馆,近期旅客投宿的订单m份接踵而至,时间从1~n天,这代表着大把大把的银子,可是他最多只能提供k间客房,更多的他只能提前去租附近的房子并赶紧装修一下,时间很紧啊。

艾瑞克找到了他最好的朋友你:“哪,这是所有的订单,你给我在1s内计算出最高峰时,超出多少间客房,这样我才能知道得去租多少房子啊。”

每张订单包含dj,sj,tj:表示从第sj日至第tj日,预定房间dj间。

住:为了简单起见,假设第一天之前宾馆所有的房间都是空的。

【输入描述】:

第一行包含两个正整数n,m,k,表示天数、订单的数量,和现有客房数。

接下来有m行,每行包含三个正整数dj,sj,tj,表示租借的数量,租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

【输出描述】:

只有一个整数,表示最高峰时还差多少客房,客房足够输出0(骗不到分)。

【样例输入】

4 3 6
2 1 3
3 2 4
4 2 4

【样例输出】

3

【数据范围及描述】:

时间:1s 空间:512M

1<=n,m<=1000,000;1<=sj<=tj<=n;1<=k,dj<=1000;

输入数据较大,最好加外挂

 
分析:
 一篇简单的DP。。。也可以用前缀和做。
 
CODE:
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 int s[1000010];
 8 void read(int &a)
 9 {
10     a=0;
11     char c=getchar();
12     while(c<'0'||'9'<c)
13         c=getchar();
14     while ('0'<=c&&c<='9')
15     {
16         a=(a<<3)+(a<<1)+c-'0';
17         c=getchar();
18     }
19 }
20 int main()
21 {
22     int n,m,dj,sj,tj,i,k;
23     cin>>n>>m>>k;
24     for (i=0;i<m;i++)
25     {
26         read(dj);
27         read(sj);
28         read(tj);
29         s[sj]+=dj;
30         s[tj+1]-=dj;
31     }
32     for (i=1;i<=n;i++)
33     {
34         s[i]+=s[i-1];
35     }
36     int mxa=0;
37     for (i=1;i<=n;i++)
38     {
39         mxa=max(s[i],mxa);
40     }
41     cout<<mxa-k;
42     return 0;
43 }
01-16 03:26