二分 以及例题

适用题型:

已经排序且需要高效查找特定元素

模板1(不加1)
int l = 0, r = n-1;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(a[mid] >= k)
            {
                r = mid;
            }
            else l = mid + 1;
        }
模板2(加1)
while(l < r)
          {
            int mid = (l + r + 1) >> 1;
            if (a[mid] > k){
              r = mid - 1;
            }
            else l = mid;
          }

例题:

1227. 分巧克力 - AcWing题库
#include<iostream>
#include<cstring>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
/* 
1.切的块数随边长增大减小:k = (wi/x)*(hi/x)
2.二分条件: f[x] >= k
 */
const int N = 1e5+10;
typedef long long ll;
int n,k;
int h[N], w[N];

bool check(int x)
{
    int num = 0;
    for(int i = 0; i < n ; i ++ )
    {
        num += ( w[i]/x ) * ( h[i]/x );
        if(num >= k) return true;
    } 
    return false;
}

int main()
{
    IOS;
    cin >> n >> k;
    for(int i = 0; i < n; i ++ ) cin >> h[i] >> w[i] ;
    
    int l = 1, r = 1e5;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1; 
    }
    cout << l ;
    return 0;
}
730. 机器人跳跃问题 - AcWing题库
#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

const int N = 1e5+10;
int n,h[N];

bool check(int e)
{
  for(int i = 1; i <= n; i ++)
  {
    e = e *2 - h[i];
    if(e >= 1e5) return true;
    if(e < 0) return false;
  }
  return true;
}
 
int main()
{
    IOS;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];

    int l = 0, r = 1e5;
    while(l < r)
    {
      int mid = l + r >> 1;
      if(check(mid)) r = mid;
      else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

相关推荐

  1. 二分 以及例题

    2024-07-20 17:28:05       31 阅读
  2. 二分与前缀和】python例题详解

    2024-07-20 17:28:05       36 阅读
  3. C语言例题(递归、二分查找、冒泡排序)

    2024-07-20 17:28:05       41 阅读
  4. 二分法中mid的处理以及STL二分函数

    2024-07-20 17:28:05       51 阅读
  5. 换页的算法以及例题

    2024-07-20 17:28:05       65 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 17:28:05       123 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 17:28:05       131 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 17:28:05       109 阅读
  4. Python语言-面向对象

    2024-07-20 17:28:05       117 阅读

热门阅读

  1. MySQL——视图

    2024-07-20 17:28:05       27 阅读
  2. Window任务栏应用图片无法加载解决方法

    2024-07-20 17:28:05       31 阅读
  3. linux shell(上)

    2024-07-20 17:28:05       31 阅读
  4. RK3588 编译opencv&opencv_contrib记录

    2024-07-20 17:28:05       35 阅读
  5. 二叉树---路径总和

    2024-07-20 17:28:05       25 阅读
  6. windows 安装 kubectl 并连接到 k8s 集群【图文教程】

    2024-07-20 17:28:05       26 阅读
  7. computeIfAbsent 和 putIfAbsent

    2024-07-20 17:28:05       27 阅读
  8. 微软Edge浏览器全解析教程

    2024-07-20 17:28:05       25 阅读
  9. 如何使用unittest框架来编写和运行单元测试

    2024-07-20 17:28:05       25 阅读