P9025 [CCC2021 S3] Lunch Concert 题解

_•́へ•́╬_ · 2023-02-05 00:01:02 · 题解

思路

把一个人转化成一个线段 [P_i-D_i,P_i+D_i]，意思是 c 在这个线段上时不需要任何时间，在左边和在右边都需要一定时间去移动。

于是我们就能得到一个分段函数。

利用离散化和差分把所有的分段函数加起来，取个最小值。

注：最小值一定在某个端点处取到。

code

#include<stdio.h>
#include<algorithm>
#define N 444444
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,lsh[N],p[N],w[N],d[N];long long a[N],b[N],ans;
inline void add(const int&l,const int&r,const int&x,const long long&y)
    {a[l]+=x;a[r+1]-=x;b[l]+=y;b[r+1]-=y;}
inline void min(long long&x,const long long&y){if(x>y)x=y;}
main()
{
    read(n);
    for(int i=0;i<n;++i)
    {
        read(p[i]);read(w[i]);read(d[i]);
        lsh[m++]=p[i]-d[i];
        lsh[m++]=p[i]+d[i];
    }
    sort(lsh,lsh+m);m=unique(lsh,lsh+m)-lsh;
    for(int i=0,x;i<n;++i)
    {
        x=p[i]-d[i];
        add(0,lower_bound(lsh,lsh+m,x)-lsh,-w[i],(long long)(w[i])*x);
        x=p[i]+d[i];
        add(upper_bound(lsh,lsh+m,x)-lsh,m,w[i],-(long long)(w[i])*x);
    }
    ans=a[0]*lsh[0]+b[0];
    for(int i=1;i<=m;++i)
    {
        a[i]+=a[i-1];b[i]+=b[i-1];
        if(a[i]>>63)min(ans,a[i]*lsh[i]+b[i]);
        else min(ans,a[i]*lsh[i-1]+b[i]);
    }
    printf("%lld",ans);
}