首页 > 其他分享 >AcWing 730. 机器人跳跃问题

AcWing 730. 机器人跳跃问题

时间:2022-11-03 09:45:46浏览次数:77  
标签:return int 机器人 730 include true 单调 AcWing

怎样使用二分来做;
看题目是否具有二段性 或者单调性;
单调性属于二段性;

怎样看单调性:
初始时E0

数学归纳法推出:Ei撇 都是大于Ei的

达到某一个值就一定能够成功,等于maxh;return true; 防止中间过程爆int

image

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100010;
int n;
int h[N];
//  查找最小值的能量e
bool check(int e){
  for(int i=0;i<n;i++){
    e=2*e-h[i];
    if(e<0){   //判断中间有没有小于0的能量
      return false;
    }else if(e>100000){  // 达到某一个值就一定能够成功,防止爆int
      return true;
    }
  }
  return true;

}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>h[i];
  }
  int l=0,r=100000;
  while(l<r){
    int mid=(l+r)/2;
    if(check(mid)){  //判断当前位置上的能量e是否满足条件
      r=mid;  // 要求找最小的能量E
    }else{
      l=mid+1;
    }
  }
  cout<<r<<endl;
  return 0;
}




标签:return,int,机器人,730,include,true,单调,AcWing
From: https://www.cnblogs.com/mengfengguang/p/16853359.html

相关文章

  • 扫地机器人地图与用户终端的同步
    以下内容为本人的学习笔记,如需要转载,请声明原文链接微信公众号「englyf」https://mp.weixin.qq.com/s/APaJheSbgTW3jNssWsp5Ng地图数据来源于机器人算法模块,一般通过SLA......
  • acwing298 围栏
    有 NN 块木板从左到右排成一行,有 MM 个工匠对这些木板进行粉刷,每块木板至多被粉刷一次。第 ii 个木匠要么不粉刷,要么粉刷包含木板 Si 的,长度不超过 Li 的连续的......
  • Jenkins发版通知企业微信机器人
    1)开始通知在Jenkins发版过程的第一步添加下面内容,调用下面脚本实现机器人发版通知(注意脚本路径和传参)${BUILD_USER}是Jenkins内置变量,执行发布的用户名,需要安装插件-Buil......
  • Codeforces 1730 D
    Codeforces1730D题意定义一次“操作”为把字符串$a$的前$k$个字母与字符串$b$的后$k$个字母交换。问能不能经过有限次操作后,让$a=b$。注:$......
  • AcWing 1221 四平方和
    \(AcWing\)\(1221\).四平方和+自定义排序(重载<)+二分一、题目大意四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多\(4\)如果把\(0\)包括进去,就正好可以表......
  • 闭社创建关注机器人,自动关注跨站用户(关联闭社、抒发森林、comin、mastodon)
    前言mastodon的跨站时间轴的显示机制有点复杂,简而言之可以这么概括“假设我处于A站,那么我发布的所有公开嘟文,都会显示在A站本站时间轴”“如果你没有被任何一个B站用户......
  • codeforces 1734C、1733D1、1733C、1730C、1729D
    1、1734CRemovingSmallestMultiples题意:给予你一个数组S,其中包含前n个正整数你可以在S上执行以下操作任多次(包含0次):1、选择一个正整数i,(1<=k<=n),并且使得数组S中......
  • AcWing 1209. 带分数
    题目条件:枚举全排列,是9个数a,b,c的位数都还不知道枚举a,b,c的位数,枚举a和b的位数,c=9-a-b判断等式是否成立//暴力dfs#include<iostream>#include<cstrin......
  • acwing第75场周赛
    这次题比较水,但是还是没能ak,自己小结一下吧第一道题就是自己枚举相加就行第二道题是一个多关键字排序,wa了几次,是因为优先级有两个是相同的需要特判一下,然后可以把字符转......
  • AcWing 1113. 红与黑
    蒟蒻只会暴搜了要点是先找到起点,从起点开始向各个方向搜DFS:(DFS当然也可以用for(inti=0;i,4;i++)来搜索四个方向,这里是个人习惯)#include<iostream>#include<cstring......