BZOJ 1696 [Usaco2007 Feb]Building A New Barn新牛舍数学-白红宇

BZOJ 1696 [Usaco2007 Feb]Building A New Barn新牛舍数学

阅读量：6039 次

发布时间：2019-06-20

本文共 1344 字，大约阅读时间需要 4 分钟。

题意:

方法:数学+模拟

解析:

首先这类问题不是第一次见了，所以直接知道拿x的中位数。y的中位数。

这题就是讨论情况很的烦。

题中有个限制，给出待求和的点不能选取。

所以假设奇数个点，求出x中位数，y中位数。

检验x,y是否存在待求和的点集里，如存在则推断四种情况。

推断的四种情况各自是(x-1,y),(x+1,y),(x,y-1),(x,y+1)，次优解一定存在于这四种情况中，这个应该很好理解？

假设不存在于原点集中。则直接求和。

假设偶数个点，则讨论全部x可取值以及y可取值就可以,建议使用容斥。

至于细节。自己研究。

代码:

#include  #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define N 10010#define INF 0x3f3f3f3f#define pa pair
            
             using namespace std;int n;int a[N];int b[N];int xx[5]={ 0,-1,1,0,0};int yy[5]={ 0,0,0,1,-1};struct node{ int x,y;}c[N];int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); c[i].x=a[i],c[i].y=b[i]; } sort(a+1,a+n+1),sort(b+1,b+n+1); if(n&1) { int tmp=n/2+1; int tmpx=a[tmp],tmpy=b[tmp]; int ans=0; int flag=1; for(int i=1;i<=n;i++) { if(tmpx==c[i].x&&tmpy==c[i].y){flag=0;break;} } if(flag) { for(int i=1;i<=n;i++) { ans+=abs(tmpx-a[i])+abs(tmpy-b[i]); } printf("%d 1\n",ans); }else { ans=INF; int cnt=0; for(int i=1;i<=4;i++) { int x=tmpx+xx[i],y=tmpy+yy[i]; int ret=0; for(int j=1;j<=n;j++) { ret+=abs(x-c[j].x)+abs(y-c[j].y); } if(ret
             
              =tmpx1&&c[k].x<=tmpx2&&c[k].y>=tmpy1&&c[k].y<=tmpy2)cnt--; ret+=abs(tmpx1-c[k].x)+abs(tmpy1-c[k].y); } printf("%d %d\n",ret,cnt); }}