本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 12:35:30

这道题我会讲解很多种思路。

30 分做法：

暴力枚举这条路的每个点， 取最小值。
时间复杂度为 $O(nt)$

70 分做法：

通过分析， 我们发现只需要考虑这 $n$ 个房子即可。（样例是迷惑你的）
为什么呢？
因为若左边的人数比右边多， 按照少数服从多数的原则， 应往左找左边那个点， 右边也一样。
若两边人数相同， 则在左边那个点到右边那个点这个区间代价是一样的。
时间复杂度为 $O(n^2)$。

100 分做法 1：

我们用前缀和和后缀和来维护， 设 $sum_i$ 为这个点左边的人走到这个点的代价，$summ_i$ 是右边的代价。
最后枚举每个点即可。
时间复杂度为 $O(n)$。
代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll n,l,x[100005],r[100005],sum[100005],summ[100005],num,numm,minn=INF;
int main(){
	cin>>l>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>r[i];
	for(int i=2;i<=n;i++){
		num+=r[i-1];
		sum[i]=sum[i-1]+(x[i]-x[i-1])*num;
	}
	for(int i=n-1;i;i--){
		numm+=r[i+1];
		summ[i]=summ[i+1]+(x[i+1]-x[i])*numm;
	}
	for(int i=1;i<=n;i++) minn=min(minn,sum[i]+summ[i]);
	cout<<minn;
	return 0;
} 

100 分做法 2：

此做法是 $70$ 分做法的强剪枝， 若左边的人数加上这栋房子的人数还没右边多， 就不需要费时间算了。
代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],sum[100005],minn=0x3f3f3f3f3f3f3f3f;
int main(){
	cin>>l>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>r[i];
		sum[i]=sum[i-1]+r[i];
	}
	for(int i=1;i<=n;i++){
		if(sum[i]>=sum[n]-sum[i]&&sum[i-1]<=sum[n]-sum[i-1]){
			ll sum=0;
			for(int j=1;j<=n;j++){
				sum+=r[j]*abs(x[i]-x[j]);
			}
			minn=min(minn,sum);
		}
	}
	cout<<minn;
	return 0;
} 

最优解：

这就是题解里大佬的思路了， 我用快读快写优化了一下， 实际就是将上述满分做法 $1$ 写成了一个循环。

k=min(r[le],r[ri]);
r[le]-=k;
r[ri]-=k;

这一段表示左右两边有 $k$ 个人已经转移完成。

ans+=k*(x[ri]-x[le]);

这是累加答案，$(x_{ri}-x_{le})$ 实际就是双方向中间走的路程和。

if(!r[le]) ++le;
if(!r[ri]) --ri;

这是左右端点转移。
最终代码：

#include<bits\/stdc++.h>
#define ll long long
using namespace std;
ll n,l,x[100005],r[100005],ans,le=1,ri,k;
long long read(){
	long long f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
void write(long long x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10){
		write(x\/10);
	}
	putchar(x%10^48);
}
int main(){
	l=read();
	ri=n=read();
	for(int i=1;i<=n;++i){
		x[i]=read();
		r[i]=read();
	}
	while(le<ri){
		k=min(r[le],r[ri]);
		r[le]-=k;
		r[ri]-=k;
		ans+=k*(x[ri]-x[le]);
		if(!r[le]) ++le;
		if(!r[ri]) --ri;
	}
	write(ans);
	return 0;
} \/\/44ms 最优解