首页 > 其他分享 >二分答案作题心得

二分答案作题心得

时间:2023-10-12 15:23:34浏览次数:51  
标签:二分 题目 int mid 作题 long 心得 check

使用洛谷P1873举例

  1. 看出这个题目考的是二分答案
  2. 找出题目横纵坐标,横坐标是我们要输出的东西(也是L和R),纵坐标是输入的m,理解题目,观察横纵坐标的递增递减关系
    1. 这个题目里面输入的m是所得到的木材,横坐标是锯片的高度,锯片越高得到的木材越少,所以是递减关系
  3. 开始写二分模板,写check函数,与check函数结果比较的是m,查看题目中有没有给出至少至多这样的字眼,找出来,以小于等于或者大于等于的字眼放到结果与m之间,至少就是小于等于
    1. 如果题目中没有至少至多,只有==m,那么就找题目中要求的横坐标的多还是少,来找到相同的m,是要左边的还是右边的,例P1182

       

  4. 输出 l 
    #include <iostream>
    using namespace std;
    const int N = 1e6 + 10;
    int a[N], n, m;
    long long check(int high){
      long long all = 0;
      for (int i = 0; i < n; ++i) {
        if (a[i] > high) all += a[i] - high;
      }
      return all;
    }
    int main(){
      ios::sync_with_stdio(0);
      cin >> n >> m;
      int l = 0, r = 0;
      for (int i = 0; i < n; ++i){
        cin >> a[i];
        r = max(r, a[i]);
      }
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid) >= m) l = mid;
        else r = mid - 1;
      }
      cout << l << endl;
      return 0;
    }

     

 

标签:二分,题目,int,mid,作题,long,心得,check
From: https://www.cnblogs.com/jienow/p/17759557.html

相关文章

  • 华为OBS使用心得及配置OBS数据禁止下载
    近期参与了一个跟华为数据交换的项目,简单聊聊华为的数据交换方案及使用心得。先简单说一下背景:数据交换旨在建立企业互信,消除数据孤岛。行业数据都是各企业花费了大量精力整理得到的,一时间公开完全不可行。但是LLM的发展,基础模型需要越来越多的数据,这在倒逼企业合作,加之......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素
    704.二分查找链接:https://leetcode.cn/problems/binary-search/description/思路:关键是定义清楚区间边界,想清楚middle在计算中是否可能取到左边界or右边界。若采用闭区间,则middle可能等于左/右边界值。27.移除元素链接:https://leetcode.cn/problems/remove-element/思路:暴......
  • 二分查找(整数二分)
    一、算法简介二分法,即二分搜索法,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法。例如,如果一个序列是有序的,那么可以通过二分的方法快速找到所需要查找的元素,相比线性搜索要快不少。此外二分法还能高效的解决一些单调性判定的问题。二分的关键不在于单调性,或者说二......
  • 代码随想录算法训练营第一天(python) | 704. 二分查找、27. 移除元素。
    Leetcode704二分查找题目链接:704二分查找关键点思路:1、是否要进入到while部分的代码是left<=right还是left<right,看[left,right]是否是合法区间.例如[1,1]是合法区间,取<=;[1,1)非合法区间,取<。2、缩小区间时,考虑边界是否已经比较过。左闭右闭区......
  • 百度飞桨应用实战暨《Python小白逆袭大神》课程学习记录及心得
    课程介绍本次课程是百度深度学习7日打卡第六期,由飞桨深度学习学院的老师进行授课。课程定位:带领零基础学员从Python进入人工智能领域,即使不懂人工智能也能学会。课程形式:B站直播加回放,微信群答疑课程亮点:使用源于产业实践的开源深度学习平台飞桨(PaddlePaddle)简单学习深度学习......
  • 寒冬之下,互联网金融的数据化建设心得
     引言:在当前经济寒冬下,互联网金融行业面临着巨大的竞争压力和市场变化。为了保持竞争优势,不断创新和适应市场需求,互联网金融企业需要进行数据化建设。本文将从策略规划、数据采集与整合、数据挖掘与分析、风险控制等方面,详细介绍互联网金融的数据化建设心得。第一部分:策略规......
  • 搜索算法:线性搜索、二分法
    搜索算法:1.线性搜索:循环遍历,判断是否等于目标值2.二分法:(需要有序)先定一个起点和终点left,right,当left<right时,取中间值mid,如果目标值小于mid,则right=mid-1,反之亦然#线性搜索defaction1(arr,target):foriinarr:ifi==target:print(arr.inde......
  • day 1 数组 704.二分查找、27.移除元素
    704.二分查找题目链接:704.二分查找视频教程文章教程思路利用middle去寻找target前提条件:这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,二分查找法返回的元素下标可能就不唯一,这些都是二分法的前提,以后看到题目描述后可以先想一想......
  • 二分法查找
    二分法原理:使用二分法一定要是先排序好的数组,如果没有排序好,比较只有可能怎么找都找不到数组:10(下标0)11121314151617181920(下标10)通过二分法查找,例如需要找出19这个元素的下标:(0+10)/2-->中间元素的下标:5拿着中间这个元素和目标要......
  • Hyperlynx使用心得
     从开始使用这个仿真软件,我们得先明白其所拥有的功能。Hyperlynx解决的是板级信号仿真,这就包括SI,PI,EMC等方面。而信号完整性又可谓是重头。https://blog.csdn.net/qq_37285073/article/details/80335293  按照自己电路板设计要求,输入层叠结构,以及相应厚度。上图显示的......