#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
vector<int> v1,v2;
int sumc[200005];
struct node{
	int p,w,d,id;
	bool operator < (node a){
		return p<a.p;
	}
}a[200005];
signed main(){
	freopen("P9025_2.in","r",stdin);
	freopen("out2.out","w",stdout);
	scanf("%lld",&n);
	v1.push_back(0);
	v2.push_back(0);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i].p,&a[i].w,&a[i].d);
		a[i].id=i;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		v1.push_back((a[i].p+a[i].d)*a[i].w);
		v2.push_back((a[i].p-a[i].d)*a[i].w);
		sumc[i]=sumc[i-1]+a[i].w;
	}
	for(int i=1;i<=n;i++){
		v1[i]+=v1[i-1];
	}
	for(int i=n-1;i>=1;i--){
		v2[i]+=v2[i+1];
	}
	cout<<"\n";
	int minn=LONG_LONG_MAX;
	for(int i=1;i<=n;i++){
		int c=a[i].p+a[i].d,dd=a[i].p-a[i].d;
		int l=0,r=n+1;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(a[mid].p>c){
				r=mid;
			}else{
				l=mid;
			}
		}
		int t=r-1;
		l=0,r=n+1;
		while(l+1<r){
			int mid=(l+r)>>1;
			if(a[mid].p>dd){
				r=mid;
			}else{
				l=mid;
			}
		}
		int tt=r-1;
		cout<<c<<","<<c*sumc[t]-v1[t]+v2[t+1]-c*sumc[n]+c*sumc[t]<<" "<<dd<<","<<dd*sumc[tt]-v1[tt]+v2[tt+1]-dd*sumc[n]+dd*sumc[tt]<<"\n";
		minn=min(minn,min(c*sumc[t]-v1[t]+v2[t+1]-c*sumc[n]+c*sumc[t],dd*sumc[tt]-v1[tt]+v2[tt+1]-dd*sumc[n]+dd*sumc[tt]));
	}
	cout<<minn;
	return 0;
}

由暴力代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p[200005],w[200005],d[200005];
signed main(){
	freopen("P9025_2.in","r",stdin);
	freopen("out1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&p[i],&w[i],&d[i]);
	}
	cout<<"\n";
	int minn=LONG_LONG_MAX;
	for(int i=1;i<=n;i++){
		int c=p[i]+d[i],dd=p[i]-d[i],sum=0,sum1=0;
		for(int j=1;j<=n;j++){
			if(i!=j){
				sum+=max(0ll,(abs(c-p[j])-d[j])*w[j]);
				sum1+=max(0ll,(abs(dd-p[j])-d[j])*w[j]);
			}
		}
		cout<<c<<","<<sum<<" "<<dd<<","<<sum1<<"\n";
		minn=min(minn,min(sum,sum1));
	}
	cout<<minn;
	return 0;
}

用前缀和优化而来，二分是为了拆掉绝对值。求助！！！WA#2#6#14