首页 > 其他分享 >每日打卡-6

每日打卡-6

时间:2023-04-17 19:22:08浏览次数:33  
标签:移走 int 岩石 mid 终点 打卡 每日 起点

一.问题描述

一年一度“跳石头”比赛又要开始了!

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

注:0<=M<=N<=5e4,1<=L<=1e9

二.设计思路

对于这些类似 “最短最长”、“最小最大” 等题目,我们使用二分答案来验证即可。

如果一个答案 x 可行,它要满足在跳跃的距离最短为 x 的时候,尽可能少移走石头。于是,我们统计在 x 的情况下,移走石头的数量 cnt 与题目要求的移走石头的数量 m 进行对比即可。now 代表当前所在的石头号,通过比对,如果发现间隔小于 x ,则必须进行一次移走石头,否则不能保证最短跳跃距离为 x。

下一步,我们需要对可能的答案进行二分查找即可。

三.流程图

 

四.伪代码 

1

五.代码实现 

1#include<bits/stdc++.h>
using namespace std;
int stone[50002];
int l, n, m;
bool check(int x){
    int cnt = 0, now = 0;
    for(int i = 1; i <= n + 1; i++){
        if(stone[i] - stone[now] < x){	
            cnt++;
        }
        else{
            now = i;
        }
    }
    return cnt <= m;
}
int binary_search(int l, int r){
    int ans;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            ans = mid;
            l = mid + 1;
        } else{
            r = mid - 1;
        }
    }
    return ans;
}

int main(){
    cin >> l >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> stone[i];
    }
    stone[n + 1] = l;
    cout << binary_search(1, l);
    return 0;
}

 

标签:移走,int,岩石,mid,终点,打卡,每日,起点
From: https://www.cnblogs.com/leapssisbird/p/17326906.html

相关文章

  • C++每日打卡
    计算长方形面积和表面积第一个函数计算长方形的面积,其中x和y是长和宽。第二个函数计算长方体的表面积,x,y和z是长,宽和高。 #include<iostream>#include<string>using namespace std;int area(int x,int y){    int a;    a=x*y;    return a;}int area(in......
  • 4.17每日学习总结
    昨天对页面功能进行一些完善,实现添加了部分功能今天上课时打算与队友进行一些沟通,对一些任务更加明确些,遇到的困难是在查找有效的问题解决方法比较耗费时间。 ......
  • 周一打卡
    1.问题描述:编写程序,实现一个简单的猜数字游戏。程序随机生成一个1~100之间的整数,让玩家猜数字,直到猜中为止。2.设计思路:程序需要用到随机数生成和输入输出。每次猜测后需要进行判断,判断猜测的数字与随机数的大小关系,提供相应提示。直到猜中为止,输出猜测的次数。3.程序流程......
  • 4.17打卡
            二.设计思路1.初始化cock,hen,chicken;2.套入循环①判断cock是否小于等于0,是则进行下一步,否则结束运算;②判断hen是否小于等于33,是则进行下一步,否则cock增加;③判断chicken是否小于等于100,是则进行下一步,否则hen增加;④代入cock,hen和chicken的值进行运算,如果价......
  • 编程打卡:C语言趣味编程习题做
    编程打卡:C语言趣味编程习题做数制转换问题描述给定一个M进制的数x,实现对x向任意非M进制的数的转换。设计思路输入M进制的数x,将x转换为十进制数,再将十进制数转换为任意非M进制的数。流程图graphA["开始"]-->B["输入M进制的数x"]-->C["将x转换为十进制数"]-->D["将十进......
  • 站立会议 —— 每日自我总结
    昨天我对修改员工信息界面和添加员工信息界面进行了ui界面美化今天我对门店信息显示界面和查询界面以及相关的按钮进行了优化,并且解决了昨天页面排版遇到的问题遇到的问题:排班表格在套用模板之后显示位置依旧不协调,无法与底版完美匹配......
  • 站立会议 —— 每日自我总结
     昨天我对修改员工信息界面和添加员工信息界面进行了ui界面美化今天我对门店信息显示界面和查询界面以及相关的按钮进行了优化,并且解决了昨天页面排版遇到的问题遇到的问题:排班表格在套用模板之后显示位置依旧不协调,无法与底版完美匹配......
  • 打卡6
    2.1个人所得税问题 //if  else就可以#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn;intmain(){ cin>>n; doubleans; if(n<3500)cout<<n;//小于起征点 else//达到了起征点 { if(n<=4500) ans=1500*(0.97)+(n-1500)*(0.9); elseif(n&......
  • 4.17打卡
    #include<iostream>#include<iomanip>#include<cmath>usingnamespacestd;intmain(){cout<<2<<endl;inti,j,k,flag;i=3;while(i<=100){j=2;k=sqrt(i);flag=1;whil......
  • 建民の每日打卡6
    一、问题描述 二、流程设计1.输入方程系数abcd2.将方程根x设为1.53.建立循环,将x赋值给x0,并按公式求出新的x。实现迭代4.当迭代满足条件后输出x值三、流程图设计 四、代码实现#include<iostream>#include<cmath>usingnamespacestd;intmain(){ floata,b,c,d,x,x0,......