题目

http://poj.org/problem?id=1723

题解

带权中位数类型的题目~

可以先考虑降维，最后集合的y坐标，明显是y坐标的中位数的位置,容易求出y方向的贡献res_y。比较麻烦的是在x坐标上最后是要列成一排，而不是单独的一个点，我们可以假设最后集合的最左边的点是x，采用贪心的策略列出公式：res_x=sum(abs(xi-x-i))(i belongs to [0,n-1])。令zi=xi-i，就转化为res_x=sum(abs(zi-x))，这相当于求zi数列的中位数（因为我们没有把重叠的点合并，所以不是带权了，直接求中位数就好，一样的意思）。

代码

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=10010;

pair<int,int> pt[maxn];

bool cmp(const pair<int,int>& a,const pair<int,int>& b){

    return a.second<b.second;

}

int n;

int main(){

    while(scanf("%d",&n)!=EOF){

        for(int i=0;i<n;i++){

            scanf("%d%d",&pt[i].first,&pt[i].second);

        }

        sort(pt,pt+n,cmp);

        int res=0;

        for(int i=0;i<n;i++){

            res+=abs(pt[i].second-pt[n/2].second);

        }

        sort(pt,pt+n);

        for(int i=0;i<n;i++){

            pt[i].first=pt[i].first-i;

        }

        sort(pt,pt+n);

        for(int i=0;i<n;i++){

            res+=abs(pt[i].first-pt[n/2].first);

        }

        printf("%d\n",res);

    }

    return 0;

}