bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍 ——中位数排序

2023-10-27 16:40

本文主要是介绍bzoj 1696: [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

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)时达到。
——————————————————————————————————
这道题很容易想到中位数 x y 也很明显可以单独考虑
但是要分奇数偶数的情况 奇数要判这个点是否有牛 没有就考虑旁边四个 
偶数就直接矩阵大小减去里面的牛就可以了 233
不过我发现题目似乎没有说没有牛在同一位置吃草 那么这里会不会有问题呢QAQ
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using std::sort;
using std::min;
const int M=2e4+7;
int read(){int ans=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}return ans*f;
}
int ans,sum,n,x[M],y[M];
struct pos{int x,y;bool operator <(const pos& h)const{return h.x!=x?h.x<x:h.y<y;}
}q[M];
std::map<pos,bool>vis;
int main(){n=read();for(int i=1;i<=n;i++){x[i]=read(); y[i]=read();q[i].x=x[i]; q[i].y=y[i];}sort(x+1,x+1+n); sort(y+1,y+1+n);int x1=x[(n+1)/2],y1=y[(n+2)/2],x2=x[(n+2)/2],y2=y[(n+1)/2];if(x1==x2&&y1==y2){bool f=false;for(int i=1;i<=n;i++)if(q[i].x==x1&&q[i].y==y1){f=true; break;}if(!f){ans=1;for(int i=1;i<=n;i++){sum=sum+abs(q[i].x-x1);sum=sum+abs(q[i].y-y1);}}else{int nx=x1,ny=y1-1;for(int i=1;i<=n;i++){sum=sum+abs(q[i].x-nx);sum=sum+abs(q[i].y-ny);}ans=1; nx=x1; ny=y1+1;int now=0;for(int i=1;i<=n;i++){now=now+abs(q[i].x-nx);now=now+abs(q[i].y-ny);}if(sum>now) ans=1;if(sum==now) ans++;nx=x1+1; ny=y1;now=0;for(int i=1;i<=n;i++){now=now+abs(q[i].x-nx);now=now+abs(q[i].y-ny);}if(sum>now) ans=1;if(sum==now) ans++;now=0;nx=x1-1; ny=y1;for(int i=1;i<=n;i++){now=now+abs(q[i].x-nx);now=now+abs(q[i].y-ny);}if(sum>now) ans=1;if(sum==now) ans++;}printf("%d %d\n",sum,ans);}else{ans=(x2-x1+1)*(y1-y2+1);for(int i=1;i<=n;i++){if(q[i].x>=x1&&q[i].x<=x2&&q[i].y>=y2&&q[i].y<=y1){if(!vis[(pos){q[i].x,q[i].y}]){ans--; vis[(pos){q[i].x,q[i].y}]=1;}}sum=sum+abs(q[i].x-x1);sum=sum+abs(q[i].y-y1);}printf("%d %d\n",sum,ans);}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/lyzuikeai/p/7604078.html

这篇关于bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍 ——中位数排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/286964

相关文章

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Python中的魔术方法__new__详解

《Python中的魔术方法__new__详解》:本文主要介绍Python中的魔术方法__new__的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、核心意义与机制1.1 构造过程原理1.2 与 __init__ 对比二、核心功能解析2.1 核心能力2.2

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Python中__new__()方法适应及注意事项详解

《Python中__new__()方法适应及注意事项详解》:本文主要介绍Python中__new__()方法适应及注意事项的相关资料,new()方法是Python中的一个特殊构造方法,用于在创建对... 目录前言基本用法返回值单例模式自定义对象创建注意事项总结前言new() 方法在 python 中是一个

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri