当前位置: 首页 > 编程日记 > 正文

POJ 2456 Aggressive cows(二分答案)

Aggressive cows
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 22674Accepted: 10636

Description

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). 

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

* Line 1: Two space-separated integers: N and C 

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output

* Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint

OUTPUT DETAILS: 

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3. 

Huge input data,scanf is recommended.

Source

USACO 2005 February Gold

 

【题意】

农夫 John 建造了一座很长的畜栏,它包括N (2 <= N <= 100,000)个隔间,这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000). 但是,John的C (2 <= C <= N)头牛们并不喜欢这种布局,而且几头牛放在一个隔间里,他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间,使任意两头牛之间的最小距离尽可能的大,那么,这个最大的最小距离是什么呢

 

【分析】

贪心+二分
二分枚举相邻两牛的间距,判断大于等于此间距下能否放进所有的牛。 

 

【代码】

#include<cstdio>
#include<algorithm>
#include<iostream>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=1e5+5;
int ans,n,m,d[N];
inline bool check(int now){int res=1,p=d[1];for(int i=2;i<=n;i++)if(d[i]-p>=now)res++,p=d[i];return res>=m;
}
int main(){n=read(),m=read();for(int i=1;i<=n;i++) d[i]=read();sort(d+1,d+n+1);int l=0,r=d[n],mid;while(l<=r){mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}printf("%d\n",ans);return 0;
}


 

转载于:https://www.cnblogs.com/shenben/p/10311950.html

相关文章:

JMeter打开脚本报错处理方法

今天电脑重装了系统&#xff0c;安装好jmeter后打开以前写的脚本&#xff0c;总是报错如下图&#xff0c;研究了半天也没搞明白。 后来一个群里的人员提醒才想起来&#xff0c;是脚本的问题&#xff0c;为啥捏&#xff1f; 因为之前写的脚本用了一些监听&#xff0c;而这些监听…

Android开发中libs包下面的mips、armeabi、armeabi-v7a和x86

简介 在Android日常的开发过程中有的项目需要引入第三方的库&#xff0c;有时候大家可能会在libs文件夹下看到 mips、armeabi、armeabi-v7a和x86这四个文件夹。那么这三个文件夹下面的包是干什么用的&#xff1f; 这三个包下面存放的用C编译的本地库文件&#xff08;各类『.…

【数据结构】判断一个单链表中各结点的值是否有序

count记录的是单链表的总长 count1记录的是升序的结点的个数 count2记录的是降序的结点的个数 如果count1或者count2等于count&#xff0c;那么就说明该序列是升序或者降序的。 稍加改进可以在准确判断是升序还是降序还是无序 &#xff08;个人认为链表中只有一个结点或者…

MSSQL-最佳实践-行级别安全解决方案

title: MSSQL-最佳实践-行级别安全解决方案 author: 风移 摘要 在SQL Server安全系列专题月报分享中&#xff0c;我们已经分享了&#xff1a;如何使用对称密钥实现SQL Server列加密技术、使用非对称密钥加密方式实现SQL Server列加密、使用混合密钥实现SQL Server列加密技术和列…

浮点数运算原理详解

导读&#xff1a; 浮点数运算是一个非常有技术含量的话题&#xff0c;不太容易掌握。许多程序员都不清楚使用操作符比较float/double类型的话到底出现什么问题。 许多人使用float/double进行货币计算时经常会犯错。这篇文章是这一系列中的精华&#xff0c;所有的软件开发人员都…

vCenter的安装

转载于:https://blog.51cto.com/yht1990/1857211

【数据结构】双链表的应用

1、设计一个算法&#xff0c;在双链表中值为y的结点前面插入一个值为x的新结点&#xff0c;即使得值为x的新结点成为值为y的结点的前驱结点。 2、设计一个算法&#xff0c;将一个双链表改建成一个循环双链表。 #include <stdio.h> #include <stdlib.h>typedef st…

Eclipse for Tricore 的安装方法

1.安装JDK32位版 2.安装Eclipse for Tricore 32位版&#xff08;应该也只有32位的&#xff09; 3.OK&#xff08;如果打开Tricore提示找不到JDK的话&#xff0c;在网上搜索如何配置JDK&#xff0c;修改环境变量&#xff09; 注意&#xff1a;Eclipse的位数必须和JDK位数相同 转…

NDK JNI方式读写Android系统的demo(二)

NDK & JNI&#xff08;方式读写Android系统的&#xff24;&#xff45;&#xff4d;&#xff4f;&#xff09; 大家都知道Android系统是一种基于Linux的自由及开放源码的操作系统&#xff0c;所以读写GPIO也可以直接用Linux那一套export/unexport方法&#xff0c;本文将介…

【数据结构】顺序串的插入算法,删除算法,连接运算,顺序串求子串算法

主函数自行添加 头文件 宏定义 #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 串的顺序存储 typedef struct {char str[MAXSIZE];int length; }seqstring; 顺序串的创建 void creat(seqstring *S) {char c;int i0;while((cgetchar())!\n){S-…

log4j日志记录级别是如何工作?

级别p的级别使用q&#xff0c;在记录日志请求时&#xff0c;如果p>q启用。这条规则是log4j的核心。它假设级别是有序的。对于标准级别它们关系如下&#xff1a;ALL < DEBUG < INFO < WARN < ERROR < FATAL < OFF。 举个栗子 下面的栗子明确指出如何可以过…

Kafka背后公司获1.25亿融资,估值超25亿美元

北京时间1月24日&#xff0c;开源Apache Kafka项目背后的公司Confluent在官方博客宣布进行了D轮融资&#xff0c;价值约为1.25亿美元&#xff0c;公司总估值高达25亿美元。 Confluent公司CEO Jay Kreps在博客中表示&#xff1a;我很高兴地宣布&#xff0c;Confluent已经募集了1…

深入学习jQuery描述文本内容的3个方法

前面的话 在javascript中&#xff0c;描述元素内容有5个属性&#xff0c;分别是innerHTML、outerHTML、innerText、outerText和textContent。这5个属性各自有各自的功能&#xff0c;且兼容性不同。jQuery针对这样的处理提供了3个便捷的方法&#xff0c;分别是&#xff1a;html(…

NDK JNI Android Studio开发与调试DEMO(三)(生成 .so 文件)

Android Studio NDK 开发与调试&#xff08;生成 .so 文件&#xff09; 温馨提示&#xff1a;如果你的 Android Studio 版本在 3.0以上 &#xff0c; 建议你用 cMake /ndk-build 的新姿势进行 NDK 开发 : https://developer.android.google.cn/index.html AS与&#xff47;&am…

字符串的模式匹配 (朴素模式匹配算法 ,KMP算法)

字符串的模式匹配 寻找字符串p在字符串t中首次出现的起始位置 字符串的顺序存储 typedef struct {char str[MAXSIZE];int length; }seqstring; 朴素的模式匹配算法 基本思想&#xff1a;用p中的每一个字符去与t中的字符一一比较。 模式p 正文 t 如果匹配成功&#xff0c…

框架页面jquery装载

转载于:https://www.cnblogs.com/moonsoft/p/10313309.html

NDKJNI Android 相关资料整理(四)

JNI/NDK开发指南 JNI/NDK开发指南&#xff08;一&#xff09;—— JNI开发流程及HelloWorld http://blog.csdn.net/xyang81/article/details/41777471 JNI/NDK开发指南&#xff08;二&#xff09;——JVM查找java native方法的规则 http://blog.csdn.net/xyang81/article/det…

【ACM】与全排列相关的STL函数 prev_permutation next_permutation

排列 与 全排列 从n个不同元素中任取m&#xff08;m≤n&#xff09;个元素&#xff0c;按照一定的顺序排列起来&#xff0c;叫做从n个不同元素中取出m个元素的一个排列。 当mn时所有的排列情况叫全排列。如果这组数有n个&#xff0c;那么全排列数为n!个。 对于全排列的求解…

虚拟机无法使用网卡桥接模式

重装了好几遍操作系统&#xff0c;换了两个虚拟机&#xff0c;差点怀疑人生…… 最终的原因竟然是win10&#xff01;&#xff01;&#xff01; 1.执行WINR 输入services.msc&#xff0c;打开服务管理器&#xff08;回车&#xff09;。 2.找到Device Install Service服务 启动此…

Azure自动化部署运维浅谈

本次来谈一谈如何在Azure中实现一些简单的自动化运维的需求&#xff0c;一般来讲自动化运维我们通过很多第三方的工具平台实现&#xff0c;比较流行的目前有很多&#xff0c;比如老牌的chef, puppet,新兴的PowerShell DSC, ansible。这些应该都是耳熟能详的了。那么在Azure平台…

NDK/JNI demo ( 五 ) ORB_SLAM2在Android上的移植过程

Android平台搭建和NDK环境配置 Android移植基础 NDK是集成的Android中调用C代码的工具包&#xff0c;核心是JNI&#xff08;Java Native Interface&#xff09;技术&#xff0c;具体这里略过不表。只说说NDK开发的基本步骤&#xff1a; 1. 编写Java代码&#xff1a;在Java中定义…

[Nancy On .Net Core Docker] 轻量级的web框架

.net core现在已经有了大的发展&#xff0c;虽然笔者现在已经从事python开发&#xff0c;但是一直在关注.net的发展&#xff0c;在逛博客园的时候&#xff0c;发现有大家都会提到Nancy这个框架&#xff0c;在简单的使用之后&#xff0c;发现竟然是如此的简单而优雅 public clas…

【算法】【ACM】深入理解Dijkstra算法(单源最短路径算法)

Dijkstra算法是用来求解从某个源点到其他各顶点的最短路径&#xff08;单源最短路径&#xff09;。 下面的Dijkstra算法的讲解都是基于这个有向图&#xff0c;在遇到其他问题可以类比。 算法的基本思想&#xff1a; 把图中的定点分成两组&#xff0c;第一组包括已确定最短路径…

智能POS常见问题整理

智能POS预警值为小于所设的数量&#xff0c;H5就会变为锁定状态 智能POS查看数据库方法&#xff1a; 商米D1&#xff1a;设置-存储设备和USB-内部存储设备-浏览-winboxcash tablet.db为智能POS数据库 Winbox文件夹内&#xff0c;为相应logcat文件&#xff0c;应用出现问题时&am…

解决安卓系统写入SD卡权限问题

1.需要用户手动赋予的权限&#xff08; Dangerous Permissions&#xff09; 所属权限组权限日历READ_CALENDAR日历WRITE_CALENDAR相机CAMERA联系人READ_CONTACTS联系人WRITE_CONTACTS联系人GET_ACCOUNTS位置ACCESS_FINE_LOCATION位置ACCESS_COARSE_LOCATION麦克风RECORD_AUDIO…

【ACM】【STL】stack应用

C Stacks&#xff08;堆栈&#xff09; C Stack&#xff08;堆栈&#xff09; 是一个容器类的改编&#xff0c;为程序员提供了堆栈的全部功能&#xff0c;——也就是说实现了一个先进后出&#xff08;FILO&#xff09;的数据结构。 操作比较和分配堆栈empty()堆栈为空则返回真…

CHUCK手把手带你搞定OPENSTACK

以下是原文链接&#xff1a;http://blog.oldboyedu.com/openstack/转载于:https://blog.51cto.com/bovin/1858198

JVM基础面试题及原理讲解

2019独角兽企业重金招聘Python工程师标准>>> 本文从 JVM 结构入手&#xff0c;介绍了 Java 内存管理、对象创建、常量池等基础知识&#xff0c;对面试中 JVM 相关的基础题目进行了讲解。 写在前面&#xff08;常见面试题&#xff09; 基本问题 介绍下 Java 内存区域…

SLAM前端 ---------特征提取之ORB(ORB与SIFT与SURF)

ORB 论文翻译&#xff1a; 一种特征匹配替代方法&#xff1a;对比SIFT或SURF 1.ORB特征简介 ORB是Oriented FAST and Rotated BRIEF&#xff08;oFAST and rBRIEF&#xff09;的简称&#xff0c;ORB的名字已经说明了其来源&#xff0c;其实ORB特征是采用FAST方法来检测提取特…

oracle 内存分配和调优 总结

一直都想总结一下oracle内存调整方面的知识&#xff0c;最近正好优化一个数据库内存参数&#xff0c;查找一些资料并且google很多下。现在记录下来&#xff0c;做下备份。 一、概述&#xff1a; oracle 的内存可以按照共享和私有的角度分为系统全局区…