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;
}