【51NOD-1108-1109距离之和最小V2V3】 排序，思维

51NOD1108距离之和最小V2

题意就是给你三维平面上的n个点，找出一个点到所有点的曼哈顿距离之和最小。
首先我们可以发现计算曼哈顿距离和时$x,y,z$是分开的，所以我们只要按照一维的方法去做，一维的方法怎么做呢，我们发现我们最终一定是找到某个数，最终的和就是这个数减去所有比他小的加上所有比他大的减去这个数，所以当这个数等于中位数的时候是最优的。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int x[maxn],y[maxn],z[maxn];
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);sort(x+1,x+1+n),sort(y+1,y+1+n),sort(z+1,z+1+n);long long ans=0;if(n%2==1){
    for(int i=1;i<=n/2;i++) ans+=x[i]+y[i]+z[i];for(int i=n/2+2;i<=n;i++) ans-=(x[i]+y[i]+z[i]);}else{
    for(int i=1;i<=n/2;i++) ans+=x[i]+y[i]+z[i];for(int i=n/2+1;i<=n;i++) ans-=(x[i]+y[i]+z[i]);}printf("%lld\n",-ans);return 0;
}

51NOD1110距离之和最小 V3

题意就是在x轴上给你n个带权值的点，要你选出一个坐标为$X_0$点，这个点到所有点的距离=$(X_0?X_i)?W_i$,要使这个点到所有点的距离之和最小，确定这个点的坐标
做法参考不带权值的这个问题，这里的权值也就相当于那个点有$w_i$个权值为1的点，所以我们只要找出中位数就可以了，但是这里拆点之后总点数可能达到1e9，我们不能通过sort找到中位数，于是我们预先算出总点数，找到中间点在哪就可以了。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
const int maxn = 1e4+10;
typedef long long ll;
struct data
{
    ll x,w;
}p[maxn];
bool cmp(const data &a,const data &b)
{
    return a.x<b.x;
}
int main()
{
    ll ans=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].w);sort(p+1,p+1+n,cmp);for(int i=1;i<=n;i++)  ans+=p[i].w;ll tt=0;ll sum1=0;for(int i=1;i<=n;i++){
    if(tt+p[i].w>=ans/2){
    sum1+=1LL*(ans/2-tt)*p[i].x;break;}else{
    tt+=p[i].w;sum1+=1LL*p[i].x*p[i].w;}}tt=0;ll sum2=0;for(int i=n;i>=1;i--){
    if(tt+p[i].w>=ans/2){
    sum2+=1LL*(ans/2-tt)*p[i].x;break;}else{
    tt+=p[i].w;sum2+=1LL*p[i].x*p[i].w;}}printf("%lld\n",sum2-sum1);return 0;
}