每日一题 Day(1)跳石头

个人主页:小则又沐风

个人专栏:<数据结构>

<竞赛专栏>

<C语言>

下面在讲解今天的算法题目的时候,我来想说明一下这个专题的讲解前提.

首先我会对这道题进行分析,然后讲解算法原理,最后讲解代码是怎么实现的.

题目:跳石头

题目讲解:

通过读题目我们知道总共包含起点,终点共N+2个石头.

我们需要实现的是通过移走石头,让最短的跳跃距离最长.

题目就是如此.

算法原理:

在解决这道题的时候我们先直接暴力解题,看看我们有什么思路能够解决这个问题.

我们就暴力枚举答案,我们知道最后的跳跃距离一定是在(1,L)中的一个数,

我们可以发现如果我们最短的跳跃距离在变大的话,我们需要移动的石头的个数也在上升,

相反跳跃距离减小的话我们需要移动的石头的个数就会下降.

所以我们可以画出下面的一个数轴.

我们假设最后我们的答案是x,那么在大于x的时候我们需要移动地石头个数一定是大于m的,

所以我们的答案一定是在左边.

当在x的左边的时候我们需要移动的石头的个数是小于等于m的,这时候我们的答案就是在这个点及其的右边的,

我们通过分析可以看出来,这个答案是具有二段性的,所以我们这道题目的算法思想就是二分答案.

我们通过设计一个函数cal(mid)来得到如果距离是mid的时候所需要移动的石头个数,

如果个数大于m的话left等于mid-1,

如果个数小于等于m的话left等于mid

以上我们算法的核心逻辑就实现了,下面我们来思考如何来实现这个cal函数,

我们来定义两个指针i,j计算这两个指针之间的距离如果距离小于我们的最小距离,那么我们需要删除的石头的个数++,此时j++,i不动直到找到了大于等于的位置,这时i移动到j的位置.

代码实现:

#include<iostream> using namespace std; typedef long long ll; const int N=5e4+10; ll a[N]; ll l,n,m; ll cal(ll x) { ll ret=0; int i=0,j=1; while(j<=n) { if(a[j]-a[i]<x) { j++; ret++; }else { i=j; j++; } } return ret; } int main() { cin>>l>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } a[n+1]=l; n++; int left=1,right=l; while(left<right) { ll mid=(left+right+1)/2; if(cal(mid)>m) { right=mid-1; } if(cal(mid)<=m) { left=mid; } } cout<<left<<endl; return 0; }

今天的每日一题到此结束.