[原创]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],在这个范围的温度下生长会生长得最好,但是不一定会提供最佳的研究价值(Lotus认为研究发育不良的盆栽也是很有研究价值的)。
Lotus进行了若干次试验,发现若第i株盆栽的生长温度适宜,可以提供ai的研究价值;若生长温度超过了适宜温度的上限,能提供bi 的研究价值;若生长温度低于适宜温度的下限,则能提供$c_i $ 的研究价值。
现在通过试验,Lotus已经得知了每一株盆栽的适宜生长温度范围,也知道了它们的a、b、c的值。你需要根据这些信息,给温室选定一个温度(这个温度可以是任意实数),使得Lotus能获得的研究价值最大。
输入描述
多组数据,第一行一个整数T表示数据组数
每组数据第一行一个整数n∈[1,50000],表示盆栽数量
接下来n行每行五个整数li,ri,ai,bi,ci∈[1,109].,意义如上所述
输出描述
每组数据输出一行一个整数表示答案
输入样例
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∗2,9∗2]=[16,18] 这样的话就能空出来一个8∗2+1=17 ,这样维护就行了.但是最后居然超时了…加了读优还是没有过。。。
然后按照题解的做法写了一发,
官方题解
首先考虑应该尝试选择哪些点:区间的左右端点、与区间左右端点距离0.5的点,这样就一定可以包括所有情况。 为了方便处理与区间左右端点距离0.5的点,只要将所有坐标扩大一倍,然后这些点就变成了“与区间左右端点距离1的点”了 考虑选出这些点后如何进行统计。显然先要将可以选的位置进行离散。假如我们选择的温度一开始是负无穷,这时答案是所有的c之和,考虑选择的温度不断升高,答案会如何变化。 每当选定的温度达到一个区间xx的左端点时,答案加上ax−cx,每当选定温度超过xx的右端点时,答案会加上bx−ax 。 维护一个数组v,初始全为0。我们在xx的左端点处加上ax−cx在xx的右端点处加上bx−ax,然后某个位置的前缀和就是选择这个位置作为最终温度的答案了。
据说这个东西叫做扫描线?!!(我计算几何白学了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; }
|