「BZOJ1696」[Usaco2007 Feb] Building A New Barn新牛舍
Description
经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃草位置，所以他想把牛舍造在最方便的地方。 每一头牛吃草的位置是一个整数点(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000)。 没有两头牛的吃草位置是相邻的。 JOHN决定把牛舍造在一个没有牛吃草的整数点上。如果牛舍在(X, Y)，在(X_i, Y_i)的牛到牛舍的距离是|X-X_i|+|Y-Y_i|。 JOHN把牛舍造在哪儿才能使所有牛到牛舍的距离和最低？
Input
第1行： 一个数，N。
第2~N+1行：第i+1行 包含第i头牛的位置(X_i, Y_i)。
Output
第1行： 两个数，最小距离和和所有可能达到这个距离和的牛舍位置的数目。
Sample Input
1 -3
0 1
-2 1
1 -1
输入解释：
一共有4头牛，位置分别为(1, -3), (0, 1), (-2, 1), 和(1, -1).
Sample Output
输出解释：
最小距离和是10，可以在牛舍位于 (0, -1), (0, 0), (1, 0), (1, 1)时达到。
题解
当n是偶数时，([x[n / 2 – 1], x[n / 2]], [y[n / 2 – 1], y[n / 2]])中的点为满足的P点，可以相应的求出距离和sum值，cnt = (x[n / 2] – x[n / 2 – 1] + 1) * (y[n / 2] – y[n / 2 – 1] + 1) – exist(x[n / 2], y[n / 2 – 1]) – exist(x[n / 2], y[n / 2] – exist(x[n / 2 – 1], y[n / 2 – 1]) – exist(x[n / 2 – 1], y[n / 2]).(其中exist返回点x[], y[]是否在n个点中，返回值为０或１,且exist()中的点必须不同）
当n是奇数时，
如果exist(x[n / 2], y[n / 2])是不在pt[]点中的话,(x[n / 2], y[n / 2])即为p点，且只有１个，再相应的统计出sum值。
否则，取点（x[n / 2] – 1, y[n / 2]), (x[n / 2] + 1, y[n / 2]),(x[n / 2], y[n / 2 – 1]),(x[n / 2], y[n / 2] + 1)进行统计，得出最优解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include<iostream> #include<cstdio> #include<algorithm> #define inf 0x7fffffff using namespace std; int n,ans[4],ans1,ans2; struct data{int x,y;}a[10001],p[4]; bool cmp1(data a,data b) {return a.x<b.x;} bool cmp2(data a,data b) {return a.y<b.y;} bool jud(int x,int y) { for(int i=1;i<=n;i++) if(a[i].x==x&&a[i].y==y)return 0; return 1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); if(n&1) { int x,y; sort(a+1,a+n+1,cmp1);x=a[(n>>1)+1].x; sort(a+1,a+n+1,cmp2);y=a[(n>>1)+1].y; if(jud(x,y)) { for(int i=1;i<=n;i++) ans1+=abs(x-a[i].x)+abs(y-a[i].y); ans2=1; } else { ans1=inf; p[0].x=x+1;p[0].y=y; p[1].x=x-1;p[1].y=y; p[2].x=x;p[2].y=y+1; p[3].x=x;p[3].y=y-1; for(int i=1;i<=n;i++) for(int j=0;j<4;j++) ans[j]+=abs(p[j].x-a[i].x)+abs(p[j].y-a[i].y); for(int i=0;i<4;i++) if(ans[i]<ans1){ans1=ans[i];ans2=1;} else if(ans[i]==ans1){ans2++;} } } else { int x1,x2,y1,y2; sort(a+1,a+n+1,cmp1); x2=a[(n>>1)+1].x;x1=a[n>>1].x; sort(a+1,a+n+1,cmp2); y2=a[(n>>1)+1].y;y1=a[n>>1].y; ans2=(x2-x1+1)*(y2-y1+1); for(int i=1;i<=n;i++) { if(a[i].x>=x1&&a[i].x<=x2&&a[i].y>=y1&&a[i].y<=y2) ans2--; ans1+=abs(x1-a[i].x)+abs(y1-a[i].y); } } printf("%d %d",ans1,ans2); return 0; } |
OI 课件=>
