The Bucket List 题解

题面:

翻译:

农夫要给n头牛挤奶,每头牛都有各自开始挤奶和结束挤奶的时间.
每头牛在挤奶的时候都需要一定数量的桶.
桶在被一头牛占用的时候,另一头牛只能用别的桶.
农夫想要知道总共需要多少个桶才能满足需求

输入:

第一行是一个数字n
之后n行,每行包括三个数字第一个数字si是奶牛开始挤奶的时间,第二个数字ti是奶牛挤奶结束的时间,第三个数字bi是奶牛在挤奶的时候需要多少个桶.

题目分析:

因为桶用完可以再给下一个用,所以我们只要保证每一个时刻每头需要挤奶的奶牛都能被满足.
我们干脆用一个数组来计算每一个时刻需要用到的桶的个数.
每次输入一头牛,那么把他挤奶的那段时间的桶都+bi.
最后把这个数组遍历一遍,找到一个时刻同时用到的桶最多是多少…
那么这个最大值就是答案.

代码:

#include<stdio.h>

int n;
int s[110], t[110], b[110];
int bucket[100000];

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &s[i] , &t[i], &b[i]);
        for(int j = s[i]; j <= t[i]; ++j){
            bucket[j] += b[i];
        }
    }
    int max = 0;
    for(int i = 0; i < 10000; ++i){
        if(max < bucket[i]) max = bucket[i];
    }
    printf("%d\n", max);
}