shu_1241 邮局选址问题

http://202.121.199.212/JudgeOnline/problem.php?cid=1078&pid=5    

分析： 因为题目中的距离是折线距离，所以可以分别考虑两个方向，又x方向与y方向实质是一样的，所以下面

            用x方向来分析。

            如图A为邮局：

            若A在x所在范围的外围，则会增加重复，所以当在x范围的中间时距离最小。（y类似）

代码：

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 10004
 
int n;
int x[MAXN],y[MAXN];
 
int my_abs(int a)
{
    return a<0? -a : a;
}
 
int calc(int s[])
{
    int sum=0;
    int mid=s[n/2];
    for(int i=0;i<n;i++) sum += my_abs(s[i]-mid);
    return sum;
}
 
void deal()
{
    int ans;
    ans=calc(x)+calc(y);
    printf("%d\n",ans);
}
 
int main()
{
    //freopen("in.txt","r",stdin);
 
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&x[i],&y[i]);
    sort(x,x+n);
    sort(y,y+n);
    deal();
    return 0;
}

shu_1241 邮局选址问题,布布扣,bubuko.com

shu_1241 邮局选址问题

原文：http://blog.csdn.net/vuorange/article/details/37608151