首页 > 代码库 > BestCoder Round #91 1002 Lotus and Horticulture
BestCoder Round #91 1002 Lotus and Horticulture
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6012
题意：
这几天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.5，右边0.5，区间端点就可以概括所有情况了。
于是，由于实数温度不好处理，可以将区间*2，左边0.5，就是-1.
然后温度是很大的数据的，从最低温开始查是不合理的，于是将温度离散化。
从最低温开始，价值就是c之和。每对于一个植物的温度，端点值加a-c，右边的值减 b-a，
那么某一个温度的价值和，就是维护的数组的前缀和。
#include <bits/stdc++.h>#define ll long longusing namespace std;int T,n;int L[50005],R[50005];ll a[50005],b[50005],c[50005];int cnt,t[300010];ll sum[300010];int main(){ scanf("%d",&T); while(T--) { scanf("%d",&n); cnt = 0; memset(sum,0,sizeof(sum)); for(int i=1; i<=n; i++) { scanf("%d%d%I64d%I64d%I64d",&L[i],&R[i],&a[i],&b[i],&c[i]); L[i] *=2; R[i] *=2; } for(int i=1; i<=n; i++) { t[++cnt]=L[i]-1; t[++cnt]=L[i]; t[++cnt]=L[i]+1; t[++cnt]=R[i]-1; t[++cnt]=R[i]; t[++cnt]=R[i]+1; } sort(t+1,t+cnt+1); cnt = unique(t+1,t+cnt+1)-t-1; //待查的温度个数 //温度离散化 for(int i=1; i<=n; i++) { L[i] = lower_bound(t+1,t+cnt+1,L[i]) - t; R[i] = lower_bound(t+1,t+cnt+1,R[i]) - t; } for(int i=1; i<=n; i++) { sum[1] +=c[i]; //最低温 sum[L[i]] +=a[i]-c[i]; sum[R[i]+1] +=b[i]-a[i]; } for(int i=1; i<=cnt+2; i++) sum[i] += sum[i-1]; ll ans = 0; for(int i=1; i<=cnt+2; i++) ans = max(ans,sum[i]); cout<<ans<<endl; } return 0;}
BestCoder Round #91 1002 Lotus and Horticulture
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。