精选文章 愤怒的牛(重回基础二分)

愤怒的牛(重回基础二分)

作者:搬砖的小孩有肉吃 时间: 2019-11-06 09:33:51
搬砖的小孩有肉吃 2019-11-06 09:33:51

https://ac.nowcoder.com/acm/contest/951/A

 

题目描述

农夫约翰建造了一座有n间牛舍的小屋,牛舍排在一条直线上,第i间牛舍在xix_ixi​的位置,但是约翰的m头牛对小屋很不满意,因此经常互相攻击。约翰为了防止牛之间互相伤害,因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局,而且几头牛放在一个隔间里,它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间,使任意两头牛之间的最小距离尽可能的大,那么,这个最大的最小距离是多少呢?

输入描述:

第一行用空格分隔的两个整数n和m;

第二行为n个用空格隔开的整数,表示位置 xix_ixi​

输出描述:

输出仅一个整数,表示最大的最小距离值。

输入

5 3
1 2 8 4 9

输出

3

说明

把牛放在1,4,8这样最小距离是3 。

 二分和三分的详解:https://www.cnblogs.com/zzh666/p/9418071.html

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long ll;
ll x[100001];
ll a[100001];
ll n,m;
//最关键的部分check
bool check(ll X){
	ll bef=x[0],total=1;//从第一个牛开始遍历,第一头牛被安排下total=1; 
	ll i;
	for(i=1;i=X){//大于距离X,符合条件 
			total++;//安排下一只牛 
			bef=x[i];//记录新安排下的牛的位置 
		}
		if(total>=m)return true;//提前安排好m个牛肯定满足条件 
	}
	return false;
}

int main(){
	scanf("%lld %lld",&n,&m);
	for(int i=0;i>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	cout<<<

 

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:“牵一发而动全身”——我用观察者模式简单模拟吃鸡

下一篇:NOI模拟 黑白划分【线段树】【容斥】

您可能感兴趣

  • TensorFlow如何提高GPU训练效率和利用率

    前言 红尘小说 https://wap.zuxs.net/ 首先,如果你现在已经很熟悉tf.data+estimator了,可以把文章x掉了╮( ̄▽ ̄””)╭ 但是!如果现在还是在进行session.run(..)的话!尤其是苦恼于GPU显存都塞满了利用率却上不去的童鞋,这篇文章或许可以给你打开新世界的大门噢( ̄∇ ̄) 如果发现经过一系列改良后训练效率大大提高了,记得回来给小夕发小红包( ̄∇...

  • 清华毕业后,一个成藤校教授,一个为比尔·盖茨"花钱",这对最强闺蜜是如何炼成的?...

    来源 | 精英说(ID:elitestalk) 《人物》对科学家颜宁的一篇专访再次把她推向微博热搜,在采访中,颜宁说道:“到了40岁,才发现这年龄前所未有的好”。 颜宁今年42岁,未婚,上个月刚获得2019年度“求是杰出科学家奖”。人们喜欢她,把她视为自己的精神偶像,不仅仅是因为她在科学领域所做出的成就,还有她笃定、丰盈的内心世界及通透、洒脱的人生观。 此前,颜宁的密友李一诺写了一篇文章——...

  • 花了三个月终于把所有的Python库全部整理了!祝你早日拿到高薪!

    链接:https://www.jianshu.com/p/2642f9d28f34 库名称简介 Chardet字符编码探测器,可以自动检测文本、网页、xml的编码。 colorama主要用来给文本添加各种颜色,并且非常简单易用。 Prettytable主要用于在终端或浏览器端构建格式化的输出。 difflib,[Python]标准库,计算文本差异 Levenshtein,快速计算字符串相似度...

  • 情感识别难?图神经网络创新方法大幅提高性能

    作者 | Kevin Shen 译者 | Monanfei 出品 | AI科技大本营(ID: rgznai100) 【导读】最近,深度学习在自然语言处理领域(NLP)取得了很大的进步。随着诸如 Attention 和 Transformers 之类新发明的出现,BERT 和 XLNet 一次次取得进步,使得文本情感识别之类的等任务变得更加容易。本文将介绍一种新的方法,该方法使用图模型在对话中...

  • 阿朱说:咨询的历史(万字深度长文)

    (1)知识成为资产:瓦特蒸汽机 13世纪的英国,首先产生了人类历史上的第一部专利保护法。不过最初是很粗糙的,授予专利的权力完全掌握在国王手中,发放专利特许证,将某种独占经营权授予工匠、商人,奖励在技术上有创新或者为英国带来利益的人。但就是因为授予权力都在国王手中,所以一开始的受益者多为封建贵族、王室的宠臣,造成了垄断业。 1598年,一位叫达西的近臣被伊丽莎白一世授予了制造和贩卖扑克牌的垄断...

  • 一个程序员的独白,行业真实工资水平,以及入行门槛

    大家好,我是一名程序员,好多人都在好奇程序员的工资水平究竟如何,这一行业被贴上诸多标签,高薪,工作累,996(早9,晚9,每周6天班),加班,年轻饭,单身狗,码农等等,现在我就从我自身和朋友们的整体状况回答一下这个问题,以及要入行的朋友们做下介绍 程序员又名软件工程师,也可以说是码农,前者是学名,后者是自嘲,为什么说码农呢,意思就是敲代码的农民,从这句话应该就能看出,这一行业的整体状况,偏累...

  • 国富论

    前言 亚当斯密的这本书标志着自由资本主义时代的到来,在看这本书时,需要结合当时的现实环境进行思考。(首次出版于1776年) 亚当斯密主张自由市场,反对政府干预垄断,认为市场有一只看不见的手会进行自我调整,但也不认为商业制度本身是完全值得肯定的;在赞扬对物质追求的同时,有鄙视商人的垄断行为和策略; 建议读者结合亚当斯密的道德情操论一起阅读,因反对政府干预垄断是建立在商人高尚的个人道德、情操之上...

  • 求你们别再学了,跟不上了!

    极客技术我是崇拜的。 我相信每个人都会关注了很多公号,种类繁多,大大小小也有上百个了吧。 我们是技术人,所以我们不和其他领域的去比,就拿技术说事儿吧。 请问,有哪个公众号能做到每天输出原创干货的? 就算是每天输出干货,有哪个号内容比我们好的? 如果你说有,请推荐给我,让我学习学习,我就闭嘴。如果没有,请你耐心听我讲述我和他的故事 我和他的故事 我叫 cxuan,石家庄人,毕业于某三本末流大学...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。