hdu 6012(离散+思路)
题目：http://acm.hdu.edu.cn/showproblem.php?pid=6012
中文题意：
nn[l,r][l,r]iiaia_ibib_icic_iaabbcc输入描述：
TTn∈[1,50000]n\in[1,50000]nnli,ri,ai,bi,ci∈[1,109]l_i,r_i,a_i,b_i,c_i\in[1, 10^9]输出：
题解：
首先需要确定哪些关键点：区间的两端以及距两端各0.5单位的位置。这样选取的所有关键位置能够覆盖所有可能的情况。为了便于后续计算，在对坐标进行放大处理后（即将所有坐标乘以2），上述关键位置就转化为了与放大后的区间两端相距1个单位的位置。接下来讨论如何统计这些关键位置的数量及对应权重的问题。显然第一步是将可选位置进行离散化处理。假设初始状态下所选温度设定为负无穷，则此时的答案即为所有权重c之和；随着温度值逐步提升时的情形，则需要动态更新当前最优解的选择范围及其对应的总权重变化情况：每当选定的温度刚好到达某个区间x左端时，则当前最优解应包含该区间的权重差a−c；而一旦选定温度超过该区间右端，则总权重需相应地增加b−a的变化量；为此我们设计了一个辅助数组v用于记录每个关键位置的重要信息：在每个区间的左端位置上记录权重差(a−c)；在右端位置上则记录增量(b−a)；随后通过计算数组v累积和的方式即可快速获得对应不同温度设定下的最优解总权重值
在实际操作中, 我采用a值低于下限来计算研究价值, 选择b值作为适宜温度范围内的研究价值, 并确定c值高于上限时的研究价值. 在对输入的所有端点进行离散化处理时, 左端点的位置变为l乘以2的位置, 并赋予其价值差值b-a（详细原因见后文）; 右端点的位置则设定为r乘以2加1的位置, 并赋予其差值c-b（详细原因见后文）. 接着对所有离散化的数据进行排序, 并按照温度梯度从低到高排列. 然后假设从最低温度开始培养全部取样点, 计算得到一个基准总价值ans. 接着从最左边的温度开始逐步枚举每个取样点的价值累加到ans中. 在相同温度下的所有取样点计算完毕后, 必须跳过已经计算过的取样位置, 仅累加未被覆盖的区域并记录当前的最大累计总和max_val. 这一过程反复执行直到所有可能的取样位置都被覆盖一遍
实现代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef struct //植物结构体
{
long long value; //价值
long long t;//温度
}Plant;
Plant plant[110000]; //最少要10W ,不然存不下
bool compare(Plant &a,Plant &b) //按温度从小到大排序
{
return a.t<b.t;
}
int main()
{
int t,n,cnt;
scanf("%d",&t);
while(t--)
{
cnt=1;
long long ans=0;
scanf("%d",&n);
int l,r,a,b,c;
for(int i=1;i<=n;i++)
{
scanf("%d %d %d %d %d",&l,&r,&b,&c,&a);
//这里的a表示低于下限的研究价值 b表示适宜温度的研究价值 c表示高于上限的研究价值
plant[cnt].value=(long long)1*(b-a);plant[cnt++].t=(long long)1*l*2; //按照左端点进行价值的叠加b-a
plant[cnt].value=(long long)1*(c-b);plant[cnt++].t=(long long )1*r*2+1;//按照右端点进行价值的累加c-b
ans+=(long long)a;
}
sort(plant+1,plant+cnt,compare);
long long test=ans;
//累加递推价值，选择最优
for(int i=1;i<cnt;i++)
{
int j=i;
test+=plant[i].value;
while(j<cnt-1 && plant[j].t==plant[j+1].t) {test+=plant[++j].value;}
i=j;
ans=max(test,ans);
}
printf("%lld\n",ans);
}
return 0;
}