当前位置: 首页 > news >正文

西安网站开发技术北京seo公司华网白帽

西安网站开发技术,北京seo公司华网白帽,沂南做网站,网站建设推广刺盾云题目描述: 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中&#xff0…

题目描述:

一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。


 输入描述:

输入文件第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来 N行,每行一个整数,第i行的整数Di(0 < Di< L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出描述:

输出文件只包含一个整数,即最短跳跃距离的最大值。


示例1:

输入 :


25 5 2 

11

14

17

21

输出:   

4

说明:

将与起点距离为2和14的两个岩石移走后,最短的跳跃距离为4(从与起点距离17的岩石跳到距离21的岩石,或者从距离21的岩石跳到终点)。


二分查找算法板子(整数):

1、左面模板

//左面模板
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

2、右面模板

//右面模板
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}

 根据样例,图解如下:

 根据如上图解,我们可以 看出根据  d  的增加,移动石头次数 m 也是逐渐增加的,所以d = 5不行,那么说明d > 5 的 情况都是不行的,所以答案是d = 4,移动次数m = 2


代码思路: 

1、写好对应的数组
2、确定好二分的板子
3、写好check函数

AC代码如下: 

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N  = 50010;
int L,n,m;
int a[N];bool check(int x)
{//cnt,表示移动石头的次数,last 表示指向没有移动过的石头int cnt = 0,last  = 0;for(int i=1;i<=n;i++){//判断一下两个石头之间的距离是否小于这个最短跳跃距离if(a[i] - a[last] < x){cnt ++; //移动石头次数增加}else{last = i; //last永远指在没被挪动的石头上面}if(cnt > m) return false;}return true;
}int main()
{scanf("%d %d %d",&L,&n,&m);//因为算是起点和终点的话是N+2个数for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[n+1] = L; //终点int l = 1,r = L;/*这里为啥不用左模板 是因为 在一个有序的数组下,我们想要找到最长的那个一定是在最右边。*/while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}

如果last那块不懂的话大家可以拿题目给的样例去手动模拟一下,好好理解代码的过程,感谢观看~

http://www.15wanjia.com/news/20092.html

相关文章:

  • 那个公司做网站郑州seo排名公司
  • 马家堡网站建设东莞公司seo优化
  • 宁波网站排名提升怎么创建一个自己的网站
  • 吴志祥最早做的网站是什么网站b2b有哪些电商平台
  • 企业网站app开发平台公司以优化为理由裁员合法吗
  • 泰兴网站建设吧网站免费客服系统
  • 东莞专业网站设计平台原创代写文章平台
  • 小程序游戏定制开发seo在中国
  • 网页设计作业个人网站商丘seo博客
  • 网站后台这么做视频教程如何进行关键词优化工作
  • 哈尔滨做网站公司企业网站seo案例
  • 按营销型网站要求重做网站 费用seo权重优化软件
  • 海南七星彩网站开发seo网络营销外包
  • 免费优化推广网站的软件上百度首页
  • 苏州家教网站建设网站快速搜索
  • 建站快车帮助百度总部客服电话
  • 泉州服装电商网站建设seo的推广技巧
  • 哪个网站可以做公务员题超级seo助手
  • 专业做网站制作百度店铺
  • 视频网站建设费用湘潭seo优化
  • 广州网站设计实力乐云seo舆情监测软件免费版
  • 工艺品网站模板考证培训机构报名网站
  • 广州做营销型网站哪家好seo优化sem推广
  • 建设厅网站企业诚信分值seo网站管理招聘
  • 网站ssl证书怎么做网店推广策划书
  • 济宁网站制作唐人站长工具官网域名查询
  • 做旅游网站seo的优化方案
  • 整站下载器 做网站地图郑州seo网站有优化
  • 王爷别来无恙短剧全集sem优化公司
  • 上海的网站名安装百度到手机桌面