hdu6012(bestcoder 91) Lotus and Horticulture(离散化+前缀和）

题意：

这几天Lotus对培养盆栽很感兴趣，于是她想搭建一个温室来满足她的研究欲望。

Lotus将所有的nn株盆栽都放在新建的温室里，所以所有盆栽都处于完全相同的环境中。

每一株盆栽都有一个最佳生长温度区间[l,r][l,r]，在这个范围的温度下生长会生长得最好，但是不一定会提供最佳的研究价值（Lotus认为研究发育不良的盆栽也是很有研究价值的）。

Lotus进行了若干次试验，发现若第ii株盆栽的生长温度适宜，可以提供a_ia​i的研究价值；若生长温度超过了适宜温度的上限，能提供b_ib​i的研究价值；若生长温度低于适宜温度的下限，则能提供c_ic​i的研究价值。

现在通过试验，Lotus已经得知了每一株盆栽的适宜生长温度范围，也知道了它们的aa、bb、cc的值。你需要根据这些信息，给温室选定一个温度（这个温度可以是任意实数），使得Lotus能获得的研究价值最大。

思路：

每种盆栽在[0,l-1],[l,r],[r,+∞].时间内有不同的价值，问选取哪个时间能有最大 价值。我的思路是用每个时间边界记录对应价值变化，[0,l-1]这个时间段对应价值c，那么我在0这个时间点记录价值加c，意味着在0以后的时间内价值都要加c，当然题目愿意是只在[0,l-1]这个区间内，所有[l,+∞]这段时间内价值是不能加c的，所以我在l这个时间点减去c，类似的，接下来两个区间的处理分别就是l时间点加a，r+1时间点减a再加b.合并之后就是在0这个时间点加c，l加a-c，r加b-a。然后让记录的这些时间点按时间大小非递减排序，用一个sum变量从时间0开始，去把每个时间对应得价值加上，答案就是这个过程中sum的最大值。但是当然没有那么简单，有一个需要注意的地方就是，离散化记录下来的时间点很有可能重复，所以我们每次更新sum的最大值的时候，不能再两个连续的时间相等的点之间更新，必须等这个时间点的操作都处理完之后再更新最大值。

代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+5;
struct node
{
    long long tem;
    long long x;
}arr[maxn*2];
bool cmp(node a, node b)
{
    if(a.tem!=b.tem) return a.tem<b.tem;
    else return a.x>b.x;
}
int main()
{
    int t;
    cin>>t;
    long long l, r;
    long long  a;
    long long  b;
    long long  c;
    while(t--)
    {
        int n;
        scanf("%d", &n);
        int i;
        for(i=0; i<3*n; i++)arr[i].x=0;
        int top=1;
        long long ans=0;
        arr[0].tem=0;
        for(i=0; i<n; i++)
        {
            scanf("%lld%lld%lld%lld%lld", &l, &r, &a, &b, &c);
            arr[0].x+=c;//时间点0开一个结构体变量即可
            arr[top].tem=l;
            arr[top].x+=a-c;//l这个时间点需要加的价值
            top++;
            arr[top].tem=r+1;
            arr[top++].x+=b-a;//r这个时间点需要加的价值
        }
        sort(arr, arr+top, cmp);
        long long sum=ans;
        for(i=0; i<top; i++)
        {
            if((i==0 || arr[i].tem!=arr[i-1].tem) && sum>ans)ans=sum;//每次到一个不同时间点时更新ans
            sum+=arr[i].x;
        }
        printf("%lld\n", ans);
    }
    return 0;
}