1696: [Usaco2007 Feb]Building A New Barn新牛舍
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 378 Solved: 168
[ Submit][ Status][ Discuss]
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
4
1 -3
0 1
-2 1
1 -1
输入解释：
一共有4头牛，位置分别为(1, -3), (0, 1), (-2, 1), 和(1, -1).
Sample Output
10 4
输出解释：
最小距离和是10，可以在牛舍位于 (0, -1), (0, 0), (1, 0), (1, 1)时达到。
对于这种题自然要先想到中位数。。不过一开始傻傻的没考虑不能建在牛身上。。。
如果是奇数，建在中间一个数的位置，偶数在中间两个的任意位置都行
不过偶数舍去区间内刚好有牛的点，如果奇数情况且最优解在牛身上
那么次优解一定在上下左右产生
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
