hdu6012-Lotus and Horticulture-离散化+前缀和

诶，又是好久没有更新，放假之后感觉就没做过什么题
一场bc的b题，并不是很难，但是想法感觉挺重要的

题目链接

题意：现在有n个植物，每个植物有个最佳温度区间，低于温度区间的产出是ci，高于温度区间的产出是bi，处于温度区间的产出是ai。现在让你选择一个温度是的产出最大，输出最大产出。

思路：一开始想到二分答案，毕竟答案范围是1e9，但是想想这个并不是单调的，二分不可行。可以发现，一共就50000个植物，那么温度点不会超过2*50000，所以可以将这些温度离散化后排个序，遍历每个温度点修改答案就行了。左端点-ci+ai,右端点-ai+bi。要注意右端点不能选择自己本身，因为这个点本身产出还是ai，所以将右端点+0.5再离散化。还有就是要注意，离散化后相同的温度点要一次处理完在更新答案……一开始在这个上面wa了一发，果然还是太挫了……

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
struct node 
{
    long long val;
    double pos;
};
int cmp(node a,node b)
{
    return a.pos<b.pos;
}
node a[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        int pos=0;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            long long a1,b1,c1;
            scanf("%lld%lld%lld",&b1,&c1,&a1);
            sum+=a1;
            a[++pos].pos=l;
            a[pos].val=-a1+b1;
            a[++pos].pos=r+0.5;
            a[pos].val=-b1+c1;
        }
        sort(a+1,a+1+2*n,cmp);
        //for(int i=1;i<=2*n;i++)printf("%lld\n",a[i].val);
        //printf("\n");
        long long maxn=sum;
        for(int i=1;i<=2*n;i++)
        {
            sum+=a[i].val;
            while(a[i].pos==a[i+1].pos)
            {
                i++;
                sum+=a[i].val;
            }
         if(sum>maxn)maxn=sum;
        }
        printf("%lld\n",maxn);
    }
    return 0;
}