[原创]HDU 6012 Lotus and Horticulture [离散化+前缀和处理]【思维】

2017-01-22 10:51:55 Tabris_ 阅读数：341

博客爬取于2020-06-14 22:42:02
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54667131

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=6012
----------------------------------------------------------------------------------------.
Lotus and Horticulture Accepts: 91 Submissions: 641
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
问题描述
这几天Lotus对培养盆栽很感兴趣，于是她想搭建一个温室来满足她的研究欲望。
Lotus将所有的nn株盆栽都放在新建的温室里，所以所有盆栽都处于完全相同的环境中。
每一株盆栽都有一个最佳生长温度区间[l,r][l,r]，在这个范围的温度下生长会生长得最好，但是不一定会提供最佳的研究价值（Lotus认为研究发育不良的盆栽也是很有研究价值的）。
Lotus进行了若干次试验，发现若第ii株盆栽的生长温度适宜，可以提供aia_i的研究价值；若生长温度超过了适宜温度的上限，能提供bib_i 的研究价值；若生长温度低于适宜温度的下限，则能提供$c_i $ 的研究价值。
现在通过试验，Lotus已经得知了每一株盆栽的适宜生长温度范围，也知道了它们的a、b、c的值。你需要根据这些信息，给温室选定一个温度（这个温度可以是任意实数），使得Lotus能获得的研究价值最大。
输入描述
多组数据，第一行一个整数T表示数据组数
每组数据第一行一个整数n∈[1,50000]n\in[1,50000]，表示盆栽数量
接下来nn行每行五个整数li,ri,ai,bi,ci∈[1,109]l_i,r_i,a_i,b_i,c_i\in[1,10^9].，意义如上所述
输出描述
每组数据输出一行一个整数表示答案
输入样例
1
5
5 8 16 20 12
10 16 3 13 13
8 11 13 1 11
7 9 6 17 5
2 11 20 8 5
输出样例
83
-----------------------------------------------------------------------------------------.
解题思路:

最开始的想法是离散化+线段树，后来想到用树状数组就行了，通过离散化后，将区间进行覆盖，至于小数的时间很好处理，只要将维护的区间值均*2操作就行了，比如说[8,9][8,9]那么维护的时候就维护[8∗2,9∗2]=[16,18][8*2,9*2]=[16,18] 这样的话就能空出来一个8∗2+1=178*2+1=17 ,这样维护就行了.但是最后居然超时了…加了读优还是没有过。。。

然后按照题解的做法写了一发,

官方题解

首先考虑应该尝试选择哪些点：区间的左右端点、与区间左右端点距离0.5的点，这样就一定可以包括所有情况。 为了方便处理与区间左右端点距离0.5的点，只要将所有坐标扩大一倍，然后这些点就变成了“与区间左右端点距离1的点”了 考虑选出这些点后如何进行统计。显然先要将可以选的位置进行离散。假如我们选择的温度一开始是负无穷，这时答案是所有的c之和，考虑选择的温度不断升高，答案会如何变化。 每当选定的温度达到一个区间xx的左端点时，答案加上ax−cxa_x-c_x，每当选定温度超过xx的右端点时，答案会加上bx−axb_x-a_x 。 维护一个数组v，初始全为0。我们在xx的左端点处加上ax−cxa_x-c_x在xx的右端点处加上bx−axb_x-a_x，然后某个位置的前缀和就是选择这个位置作为最终温度的答案了。

据说这个东西叫做扫描线？！！（我计算几何白学了hhh），学习一波。。。
其实就是个前缀和处理，然后从左到右扫描而已。

但是写出来还是超时了，当时我离散化的方式的map，于是看了别人写的二分，写了一发二分，这样才过了这道题。。最后 1912ms AC。。。。

附本题代码
-----------------------------------------------------------------------------------------.

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 50000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}


/***********************************************************************/
struct input{
    int l,r,a,b,c;
}a[N];
int lr[N<<1],cnt;
LL rr[N<<1],ll[N<<1];

int h(int x){
    int l=0,r=cnt,mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(lr[mid]<=x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int main(){
    int _;
    s1(_);
    while(_--){
        int n;
        s1(n);
        cnt = 0;

        Rep(i,1,n) {
            a[i].l=read();
            a[i].r=read();
            a[i].a=read();
            a[i].b=read();
            a[i].c=read();

            lr[++cnt]=a[i].l;
            lr[++cnt]=a[i].r;
        }
        sort(lr+1,lr+n*2+1);
        cnt = unique(lr+1,lr+n*2+1)-(lr+1);
        //Rep(i,1,cnt){printf("%d\n",lr[i]);}

        Rep(i,0,cnt)  rr[i]=ll[i]=0ll;

        LL ans = 0ll,mx = 0ll;
        Rep(i,1,n){
            ans+=a[i].c;
            rr[h(a[i].l)]+=a[i].a-a[i].c;
            ll[h(a[i].r)]+=a[i].b-a[i].a;
        }

        mx=ans;
        Rep(i,1,cnt){
            ans+=rr[i];
            mx=max(mx,ans);
            ans+=ll[i];
            mx=max(mx,ans);
        }
        printf("%I64d\n",mx);
    }
    return 0;
}