【HDU】6012 Lotus and Horticulture （BC#91 T2）

【算法】离散化

【题解】

答案一定存在于区间的左右端点、与区间左右端点距离0.5的点上

于是把所有坐标扩大一倍，排序（即离散化）。

让某个点的前缀和表示该点的答案。

初始sum=∑c[i]

在l[i]处加上a[i]-c[i]，在r[i]+1处加上b[i]-a[i]。

从左到右计算sum并比较出最大值即可。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#include<iostream>
using namespace std;
const int inf=0x3f3f3f3f,maxn=50010;
struct cyc{int x,y;}a[maxn*3];
long long ans,sum;
int n,A,B,C,D,E,cnt;
bool cmp(cyc a,cyc b)
{return a.x<b.x;}
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;
}
int main()
{
    int T=read();
    while(T--)
     {
         int n=read();sum=0,cnt=0;
         for(int i=1;i<=n;i++)
          {
              A=read(),B=read(),C=read(),D=read(),E=read();A*=2;B*=2;
              sum+=E;
              a[++cnt].x=A,a[cnt].y=C-E;a[++cnt].x=B+1,a[cnt].y=D-C;
         }
        sort(a+1,a+cnt+1,cmp);
        ans=sum;
        for(int i=1,now=1;i<=cnt;i++)
         {
             while(now<=cnt&&a[now].x==a[i].x){sum+=a[now].y;now++;}
             ans=max(ans,sum);
         }
        printf("%lld
",ans);
     }
    return 0;
}