题目链接
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1110
题意
X轴上有N个点，每个点除了包括一个位置数据X[i]，还包括一个权值W[i]。点P到点P[i]的带权距离 = 实际距离 * P[i]的权值。求X轴上一点使它到这N个点的带权距离之和最小，输出这个最小的带权距离之和。
题解
设答案为ans。那么
ans=sigma (abs(x[i] - pos) * w[i]).
对答案ans的贡献来源于两方面：x[i]和w[i].
根据乘法的含义，a*b相当于b个a相加。
那么w[i]的贡献就是将x[i]的贡献提供了w[i]份。即可以将一个点看作w[i]个点。
然后就是一维距离之和最小问题了，显然位置在中位数上最小。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;struct node
{int x,w;node(){}node(int x,int w):x(x),w(w){}bool operator<(const node &o)const{return x<o.x;}
}a[maxn];int main()
{int n;while(~scanf("%d",&n)){int m=0;for(int i=0;i<n;i++){int u,v;scanf("%d%d",&u,&v);m+=v;a[i]=node(u,v);}sort(a,a+n);int p=m/2;//要选的值是第p个int sum=0,pos=0;for(int i=0;i<n;i++){sum+=a[i].w;if(sum>=p){pos=a[i].x;break;}}long long ans=0;for(int i=0;i<n;i++){long long tmp=(long long)abs(a[i].x-pos)*(long long)a[i].w;// cout<<tmp<<endl;ans+=tmp;}printf("%lld\n",ans);}return 0;
}