# 洛谷P2874 [USACO07FEB]新牛棚Building A New Barn [贪心]

2022年11月23日
0 收藏 613 点赞 4,923 浏览 2389 个字

## 题目描述

After scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots of all N (2 ≤ N ≤ 10,000 cows. Each grazing spot is at a point with integer coordinates (Xi, Yi) (-10,000 ≤ Xi ≤ 10,000; -10,000 ≤ Yi ≤ 10,000). The hungry cows never graze in spots that are horizontally or vertically adjacent.

The barn must be placed at integer coordinates and cannot be on any cow’s grazing spot. The inconvenience of the barn for any cow is given the Manhattan distance formula | X – Xi | + | Y – Yi|, where (X, Y) and (Xi, Yi) are the coordinates of the barn and the cow’s grazing spot, respectively. Where should the barn be constructed in order to minimize the sum of its inconvenience for all the cows? 给出平面上n个不相邻的点，要求到这n个点的曼哈顿距离之和最小的点的个数ans2，和这个最小距离ans1。

## 输入输出格式

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains two space-separated integers which are the grazing location (Xi, Yi) of cow i

Line 1: Two space-separated integers: the minimum inconvenience for the barn and the number of spots on which Farmer John can build the barn to achieve this minimum.

## 输入输出样例

`41 -30 1-2 11 -1`

`10 4`

## 说明

The minimum inconvenience is 10, and there are 4 spots that Farmer John can build the farm to achieve this: (0, -1), (0, 0), (1, 0), and (1, 1).

分析：由题意可以得出，ans2=∑(|x-x[i]|+|y-y[i]|)，那么很显然越是靠中的点ans2就会越小，那么就要分情况来考虑，如果n是奇数，那么就直接由各个点的中位点来算（也就是排序以后得到一个x[n/2+1],y[n/2+1]），但是要求不能有已经给出的点，所以要在(x,y+1),(x+1,y),(x-1,y),(x,y-1)四个点，即上下左右每个点进行计算和判断。如果n是偶数，那么排序以后得到的是一个2*2的矩阵，那么就在这个矩阵中对每个点进行计算判断。具体看代码。

Code：

`//It is made by HolseLee on 21st Apr 2018#include<bits/stdc++.h>using namespace std;const int N=1e4+;int n,ans,cnt;int dx[]={,,,-};int dy[]={,-,,};struct Node{  int x,y;}a[N];bool cmpx(Node a,Node b){return a.x<b.x;}bool cmpy(Node a,Node b){return a.y<b.y;}inline int Abs(int x){return x>?x:-x;}bool judge(int x,int y){  for(int i=;i<=n;i++)    if(a[i].x==x&&a[i].y==y)      return false;    else return true;}int getans(int x,int y){  int ret=;  for(int i=;i<=n;i++)    ret+=(Abs(a[i].x-x)+Abs(a[i].y-y));  return ret;}int main(){  ios::sync_with_stdio(false);  cin>>n;  int x,y;  for(int i=;i<=n;i++)    cin>>a[i].x>>a[i].y;  if(n%==){    sort(a+,a+n+,cmpx);    x=a[n/+].x;    sort(a+,a+n+,cmpy);    y=a[n/+].y;    ans=N<<;cnt=;    for(int i=;i<;i++){      int X=x+dx[i],Y=y+dy[i];      int num=getans(X,Y);      if(num<ans)ans=num,cnt=;    else if(num==ans)cnt++;    }  }  else{    sort(a+,a+n+,cmpx);    int xs=a[n/].x,xe=a[n/+].x;    sort(a+,a+n+,cmpy);    int ys=a[n/].y,ye=a[n/+].y;    cnt=(xe-xs+)*(ye-ys+);    for(int i=;i<=n;i++){      if(a[i].x>=xs&&a[i].y>=ys&&a[i].x<=xe&&a[i].y<=ye)    cnt--;      ans+=(Abs(a[i].x-xs)+Abs(a[i].y-ys));    }  }  cout<<ans<<" "<<cnt<<"\n";  return ;}`

python开发_常用的python模块及安装方法
adodb：我们领导推荐的数据库连接组件bsddb3：BerkeleyDB的连接组件Cheetah-1.0：我比较喜欢这个版本的cheeta…

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com