题目意思是一个人要做研究,现在要你计算植物在特定温度下的研究价值,给定一个区间,区间以上,区间内,区间以下三个段位是不同的价值。植物很多,而且每盆植物都有自己的区间价值,然后现在要你计算出研究价值最大的那个温度。


一开始也不知道自己再想什么玩意儿,虽然想到了贪心但是却在乱做,后来看了题解~我们可以从最低的温度开始慢慢往上计算。在输入数据时就要把位置设置好了,然后赋值,所以肯定需要一个结构体来存咯。要注意的一点是有些特殊的点,就是所有区间都不存在的,具体请看代码,不过另外看了一个用map做的,更加6啊。


代码:

StatusAccepted
Time1716ms
Memory3296kB
Length934
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;
#define MAX 50005
int t, n, l, r, a, b, c;
long long ans, base;
struct Res{
    double pos;
    int val;
    bool operator<(const Res&x){
        return pos<x.pos;
    }
}res[MAX*2];
int main()
{
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        ans=0;
        base=0;
        for(int i=0;i<n;i++){
            scanf("%d%d%d%d%d", &l, &r, &a, &b, &c);
            base+=c;
            res[i].pos=l;
            res[i].val=a-c;
            res[i+n].pos=r+0.5;
            res[i+n].val=b-a;
        }
        sort(res, res+n*2);
        for(int i=0;i<n*2;i++){
            base+=res[i].val;
            while(i+1<n*2&&res[i].pos==res[i+1].pos){
                i++;
                base+=res[i].val;
            }
            if(base>ans)ans=base;
        }
        printf("%lld\n", ans);
    }
    return 0;
}


map版本:

StatusAccepted
Time1248ms
Memory5752kB
Length646
LangC++
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
#define LL long long
map<int, LL> res;
int t, n, l, r, a, b, c;
LL ans, now;
int main()
{
    scanf("%d", &t);
    while(t--){
        res.clear();
        ans = 0;
        now = 0;
        scanf("%d", &n);
        while(n--){
            scanf("%d%d%d%d%d", &l, &r, &a, &b, &c);
            res[0]+=c;
            res[l*2] += a-c;
            res[r*2+1] +=b-a;
        }
        for(map<int , LL>::iterator it=res.begin();it!=res.end();it++){
            now+=it->second;
            ans=ans>now?ans:now;
        }
        printf("%lld\n", ans);
    }
    return 0;
}