首页 > 编程语言 >C++ | 二分(重点二分答案)

C++ | 二分(重点二分答案)

时间:2024-03-13 20:03:03浏览次数:31  
标签:二分 int ll mid C++ 答案 using check

常见的二分类型:

1. 整数二分

2. 小数二分(相对较少)

3. 二分答案(最常见)

二分最直接的思想就是用O(logn)的时间较快的在数组中找见想要找的边界数,枚举时间较慢O(n)。 小数二分与整数二分的思想相一致,就不在赘述了。

☆ 理解二分一定要理解的问题是答案取得是区间的右边界,则返回的是l,取区间的左边界,则返回的是r,下面用一张图来详细讲解。

整数二分的模版:

//找到升序数组a中的第一次出现的位置
int l = 0, r = 1e9;
//注意这里的判断条件,这样可以保证l,r最终一定收敛到分界点
while (l + 1 != r) {
    int mid = (l + r) >> 1;//l,r相邻退出
    
    //如果a为升序,说明mid偏大了,需要减小mid,将r变小
    if (a[mid] >= x) r = mid;
    else l = mid;
}
cout << r << '\n';

下面就是一道经典的整数二分 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int data[200];
  for (int i = 0; i <200; i ++) data[i] = 4 * i + 6;
  int l = -1, r = 199;
  int x;cin >> x;

  while (l + 1 != r) {
    int mid = (l + r) >> 1;
    if (data[mid] >= x) r = mid;
    else l = mid;
  }
  cout << r;
}

 二分答案的核心语句:

if (check(mid) >= m ) l = mid;

else r = mid;

check()函数的编写,我的做法是:

先遍历一遍题目中的数组,然后定义一个lst表示上一个数求出两者之间的差值,最后判断这个数值与体重条件的关系,最后返回与check函数值相比将的值。

       这里问题的关键就在于理解距离和岩石数的转换以及mid和check所表示的是什么,最短的跳跃距离正相关于至多移走的岩石数,移走的岩石数越多,最短距离越大,mid表示的是两个相邻之间的距离,check记录的则是移走的岩石的数量,当两块石头中间的距离不够mid的时候,去掉后一块石头,特例判断就是最后一块石头不能去掉。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e4 +9;
int a[N], L, n, m;

int check(int mid) {
  int res = 0, lst = 0;//lst表示上一块岩石
  for (int i = 1; i <= n; i++) {
    if (a[i] - a[lst] < mid)
    {
      res ++;
      continue;
    }
    lst = i;
  }
  if (L - a[lst] < mid) return m + 1;
  return res;
}

int main() {
  cin >> L >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];

  ll l = 0, r = 1e9;
  
  while (l + 1 != r) {
    int mid = (l + r) >> 1;
    if (check(mid) <= m) l = mid;
    else r = mid;
  }
  cout << l;
  return 0;
}

 很明显这题中的两个数值的转换是负相关的,解题的过程中要注意的是输入的数组不一定是有序的,要排序。check里要判断lst是存在的。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N];
int n, m;

int check(int mid) {
  int lst = 0,res = 0;
  for (int i = 1; i <= n; i++) {
    if (lst && a[i] - a[lst] < mid) continue;
    res ++;
    lst = i;
  }
  return res;
}

int main()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >>a[i];
  sort(a +1, a + 1 + n);

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

 

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, k;

ll check(ll mid) {
  ll res = 0;
  for (int i = 1; i <= n; i++) res += min(m, mid /i);
  return res;
}

int main()
{
  cin >> n >> m >> k;
  ll l = 0, r = 1e14;
  while (l + 1 != r) {
    ll mid = (l + r) >> 1;
    if (check(mid) >= k) r = mid;
    else l = mid;

  }
  cout << r;
  return 0;
}

标签:二分,int,ll,mid,C++,答案,using,check
From: https://blog.csdn.net/lly18435759909/article/details/136632701

相关文章

  • 04_C++字符串_vector使用
    1.初始化vector vector<int>v1;默认初始化vector<int>v2(10);10个int类型的元素,初始化值为-1vector<string>v3{"a","bb","ccc"};列表初始化,包括三个元素2.向vector添加元素#include<iostream>#include<string>#include<vector>......
  • windbg 调试 c++ std::exception
    由于c++std::exception在windbg里面调用堆栈显示不正确,可以通过加载了系统pdb和软件pdb后,!analyze-v可以分析出来,所有需要配置系统pdb。1、把exe,pdb放到同一个目录下。2、加载dmp文件(拖动dmp文件到windbg)。3、设置pdb路径:File->SymbolFilePath,比如D:\Desktop\3dLayer,记得加......
  • C++纯虚函数和抽象类
    在C++中,可以将虚函数声明为纯虚函数,语法格式为:virtual返回值类型函数名(函数参数)=0;纯虚函数没有函数体,只有函数声明,在虚函数声明的结尾加上=0,表明此函数为纯虚函数。最后的=0并不表示函数返回值为0,它只起形式上的作用,告诉编译系统“这是纯虚函数”。包含纯虚函数的类称......
  • 突破编程_C++_C++11新特性(模板的改进与细节)
    1模板右尖括号的改进在C++11之前,模板的解析和实例化过程中,右尖括号>的处理有时会导致一些意外的结果,特别是在嵌套模板或模板模板参数中。这是因为C++编译器通常会试图“查看前方”来确定何时结束模板参数的列表,这有时会导致解析错误。C++11对模板的右尖括号处理进......
  • 【C++】thread 头文件无法正常使用问题
    问题当我使用MinGWGCC,在windows上编写C++程序的时候,使用thread类会无法编译,有如下错误:我使用的是c++17这个问题原因是MinGWGCC当前仍缺少标准C++11及以上版本线程类的实现。解决方案Stackoverflow上的类似问题:传送门1.下载源文件:源文件外网可能比较慢,提供C......
  • C++多态和虚函数
    C++多态和虚函数#include<iostream>usingnamespacestd;//基类PeopleclassPeople{public:People(char*name,intage);voiddisplay();protected:char*m_name;intm_age;};People::People(char*name,intage):m_name(name),m_age(age){}......
  • C++初阶:1_C++入门
    C++入门零.本节知识点安排目的C++是在C的基础之上,容纳进去了面向对象编程思想,并增加了许多有用的库,以及编程范式等。熟悉C语言之后,对C++学习有一定的帮助,本章节主要目标:补充C语言语法的不足,以及C++是如何对C语言设计不合理的地方进行优化的,比如:作用域方面、IO方面、函数......
  • 浅淡 C++ 与 C++ 入门
            我们知道,C语言是结构化和模块化的语言,适用于较小规模的程序。而当解决复杂问题,需要高度抽象和建模时,C语言则不合适,而C++正是在C的基础之上,容纳进去了面向对象编程思想,并增加了许多有用的库,以及编程范式。        因此在这篇博客,将会介绍C++中引入哪些......
  • c++内建函数对象
    概念:c++STL中内建了一些函数对象分类:算术仿函数关系仿函数逻辑仿函数用法:这些仿函数所产生的对象,用法和一般函数完全相同使用内建函数对象,需要使用头文件#include<functional> 1.算术仿函数 功能描述:实现四则运算其中negate是一元运算,其他都是二元运算仿函数......
  • C++ cout的使用总结
    cout是C++中ostream类型的对象cout是C++中ostream类型的对象,该类被封装在<iostream>库中,该库定义的名字都在命名空间std中,所以cout全称是std::cout。1、cout支持多种数据类型,如int、float、double、char、string等,它们都会被自动转换成字符串进行输出。#includ......