二分答案
程序员文章站
2022-03-11 20:52:59
...
基本算法 二分答案 《跳石头》
这是一道经典题目,出处为noip2015,也就是我参加OI的第一年
题目描述:
一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。
输入描述:
输入文件第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来N行,每行一个整数,第i行的整数Di(0 < Di < L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出描述:
输出文件只包含一个整数,即最短跳跃距离的最大值。
数据约定:
对于20%的数据,0≤M≤N≤10。
对于50%的数据,0≤M≤N≤100。
对于100%的数据,0≤M≤N≤50,000,1≤L≤1,000,000,000。
本文不讲述20分,70分做法
- 本题的正解是使用二分答案。所谓二分答案,就是从答案入手去解决问题,有的时候由题目正推不好得到答案,或者是复杂度太高。恰巧输出要求是一个数值,那么我们可以从数值回推,验证是不是答案即可。
- 二分是对于寻找答案的描述。即我们知晓了数据范围,或者答案可能存在的范围,从而用二分法去缩小答案的范围,最终确定答案。
对于本题的思路:
1.答案输出一个整数,因此我们从最小距离的最大值下手。
2.L即河的宽度是从0到1000000000,因此我们的答案可能是从0到1000000000
3.那我们写一个二分好了
4.我们写一个check函数,参数是我们二分中的mid,返回的是根据答案推出拿掉的石头数量
int check(int ans){
/* ... */
return tot;
}
5.那函数怎么写呢?我们从题目输入的数据来看,很像是给了我们一串前缀和!因此我们任意两个石头之间的距离就可以表示成前缀和的差值。我们从出发点(注意不是第一块石头)开始计算,如果两个石头之间的距离小于我们之前给定的答案,就拿掉下一块石头,然后继续判定(这里显然是一个while循环)。然后返回我们拿掉的石头总数。
6.这次我们又回到main函数了,我们每一个拿到的“答案”都对应了一个拿掉的石头数。那么答案是哪一个?题目给定了拿掉石头的最大值,那么就是最接近这个值的答案啦!
AC代码(每个数据点不超过20ms):
#include<cstdio>
#include<algorithm>
#include<iostream>
#define maxn 50010
using namespace std;
int n,m,l;
int a[maxn];
int check(int t){
int re=0,now=0;
while(now<=n){
int len=a[now+1]-a[now];
if(len>=t){
now++;
continue;
}
while(len<t){
if(now+2<=n+1){
len=len+(a[now+2]-a[now+1]);
re++;
now++;
}
else{
now++;
re++;
break;
}
}
now++;
}
return re;
}
int main(){
scanf("%d%d%d",&l,&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
a[n+1]=l;
int head=1,tail=1000000000;
int mid,ans=0;
while(head<tail){
mid=(tail+head)/2;
if(mid==head) break;
int p=check(mid);
if(p>m)
tail=mid;
else {
if(mid>ans) ans=mid;
head=mid;
}
}
printf("%d",ans);
return 0;
}
本文代表个人思路以及见解,欢迎广大OIer进行指正。最后祝各位OIer武运昌隆。
上一篇: html5在工作中主要干什么
推荐阅读
-
java面试宝典APP(java基础面试题及答案)
-
小明没有喝酒却被查出酒驾他很可能是刚喝完什么 蚂蚁庄园小课堂12月2日答案
-
小鸡宝宝考考你世界上最小的海是 12月5日蚂蚁庄园课堂答案
-
小鸡宝宝考考你下面哪种鱼不属于鱼类 蚂蚁庄园12月4日课堂答案
-
高二分科怎么选择3+1+2?高一选科怎么选最好?
-
2015华胥引全网独播活动正确答案分享 答题抽QB 好莱坞会员
-
小明工作日加班到晚上11点 他加班时薪应不低于?蚂蚁庄园4月12日答案
-
漂浮在天空中的一朵云可能有多重 支付宝蚂蚁庄园4月14日答案
-
月牙泉位于我国哪个省份 支付宝蚂蚁庄园4月4日答案
-
二分法(二):采用二分法解决“最小化最大值问题”