首页 > 代码库 > BZOJ 1696 [Usaco2007 Feb]Building A New Barn新牛舍 数学
BZOJ 1696 [Usaco2007 Feb]Building A New Barn新牛舍 数学
题意:链接
方法:数学+模拟
解析:
首先这类问题不是第一次见了,所以直接知道拿x的中位数。y的中位数。
这题就是讨论情况很的烦。
题中有个限制,给出待求和的点不能选取。
所以假设奇数个点,求出x中位数,y中位数。
检验x,y是否存在待求和的点集里,如存在则推断四种情况。
推断的四种情况各自是(x-1,y),(x+1,y),(x,y-1),(x,y+1),次优解一定存在于这四种情况中,这个应该很好理解?
假设不存在于原点集中。则直接求和。
假设偶数个点,则讨论全部x可取值以及y可取值就可以,建议使用容斥。
至于细节。自己研究。
代码:
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10010
#define INF 0x3f3f3f3f
#define pa pair<int,int>
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<ans)ans=ret,cnt=1;
else if(ret==ans)cnt++;
}
printf("%d %d\n",ans,cnt);
}
}else
{
int tmpx1=a[n/2],tmpx2=a[n/2+1];
int tmpy1=b[n/2],tmpy2=b[n/2+1];
int ret=0,cnt=(tmpx2-tmpx1+1)*(tmpy2-tmpy1+1);
for(int k=1;k<=n;k++)
{
if(c[k].x>=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);
}
}
BZOJ 1696 [Usaco2007 Feb]Building A New Barn新牛舍 数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。