P5117 [USACO18DEC]The Bucket List B

[USACO18DEC]The Bucket List B

题目描述

Farmer John 正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。他认为这最终能使得他使用数量更少的桶，然而他不清楚具体是多少。请帮助他！

Farmer John 有 $N$ 头奶牛（$1\le N\le 100$），方便起见编号为 $1\dots N$。 第 $i$ 头奶牛需要从时间 $s_i$ 到时间 $t_i$ 之间挤奶，并且挤奶过程中需要用到 $b_i$ 个桶。于是多头奶牛可能在同一时刻都在挤奶；如果这样，他们不能使用相同的桶。也就是说，一个在第 $i$ 头奶牛挤奶时用的桶不可以被任何在时间 $s_i$ 到时间 $t_i$ 之间挤奶的其他奶牛使用。当然，这个桶在这段时间之外可以被其他奶牛所使用。为了简化他的工作，FJ 保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的 $s_i$ 和 $t_i$ 各不相同）。

FJ 有一个储藏室，里面有依次编号为 $1$、$2$、$3$、……的桶。在他的挤奶策略中，当某一头奶牛（比如说，奶牛 $i$）开始挤奶（在时间 $s_i$），FJ 就跑到储藏室取出编号最小的 $b_i$ 个桶分配给第i头奶牛用来挤奶。

请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

输入格式

输入的第一行包含 $N$。以下 $N$ 行，每行描述了一头奶牛，包含三个空格分隔的数 $s_i$，$t_i$，和 $b_i$。 其中 $s_i$ 和 $t_i$ 均为 $1\dots 1000$ 之间的整数，$b_i$ 为 $1\dots 10$ 之间的整数。

输出格式

输出一个整数，为 FJ 需要的桶的数量。

样例 #1

样例输入 #1

3
4 10 1
8 13 3
2 6 2
1
2
3
4

样例输出 #1

4
1

提示

在这个例子中，FJ 需要 $4$ 个桶：他用桶 $1$ 和桶 $2$ 来给奶牛 $3$ 挤奶（从时间 $2$ 开始）。他用桶 $3$ 给奶牛 $1$ 挤奶（从时间 $4$ 开始）。当奶牛 $2$ 在时间 $8$ 开始挤奶时，桶 $1$ 和桶 $2$ 可以再次利用，然而桶 $3$ 不可以，所以他会使用桶 $1$、桶 $2$ 和桶 $4$。

代码

#include

using namespace std;

int a[10000];

int s,t,b;

int n;

int maxx=-100;

int  main()
{
	memset(a,0,sizeof(0)); 
	
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>s>>t>>b;
		
		a[s]=b;
		a[t]=-b;
	}
	
	int ans=0;
	
	for(int i=1;i<=1010;i++)//t最大为1000 
	{
		ans+=a[i];
		
		maxx=max(maxx,ans);
	}
	
	cout<<maxx;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39