自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:44:42，当前版本为作者最后更新于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);
}