C++二分知识模板与例题_C

二分查找：二分查找是基于有序序列的查找算法，该算法一开始令[lift,rigth]为整个序列的下标区间，然后每次测试当前[lift,rigth]的中间位置mid=(lift+rigth)/2,判断mid与预查询的元素x的大小。

二分查找的高效之处在于，每一步都可以去除当前区间中的一半元素，因此其时间复杂度是O(logn)。

二分做题模板：

例题1：

789.数的范围
给定一个按照升序排列的长度为n的整数数组,以吸q个查询。

对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。

如果数组中不存在该元素,则返回 -1 -1 。

输入格式
第一行包含整数n和q,示数组长度和询问个数。

第二行包含n个整数(均在1 ~ 10000范围内),表示完整数组。

接下来q行，每行包含一个整数 k,表示一个询问元素。

输出格式
共q行,行包含两个整数,表示所求元素的起始位置和终止位置。

如果数组中不存在该元素,则返回 -1 -1 。

数据范围
1≤n≤100000
1 < q≤10000
1 输入样例:
6 3
1 2 2 3 3 4

3
4

输出样例:
3 4
5 5
-1 -1

#include
#include
#include
#include
#include
#include       
#include
#include
#include
#include
#include
using namespace std;
const int N = 100010;
int n, q;
int a[N];
int main()
{
    cin>>n>>q;
    for(int i=0;i>a[i];//遍历数组； 
	}
	while (q--)// q次查询； 
	{
		int x;
		cin>>x;//x就是我们在数组中要找的数 
		int l=0,r=n-1; 
		while(l>1; //首先要找到>=x的第一个数，这样我们就可以找到第一个数的下标 
			if(a[mid]>=x)//当a[mid]>= x时，说明mid及其左边可能含有值为x的元素
			{
				r=mid;//所以将mid赋值给r，缩小一半范围 
			}
			else
			{
				l=mid+1;//否则，就是a[mid]>1;
				if(a[mid]

 
例题2： 
 题目 1885:  
蓝桥杯2017年第八届真题-分巧克力 
题目描述
 儿童节那天有K位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。


 小明一.共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。


 为了公平起见，小明需要从这N块巧克力中切出K块巧克力分给小朋友们。

切出的巧克力需要满足:
 1.形状是正方形，边长是整数
 2.大小相同
 例如一.块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

.
 当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么?
 输入
 第一行包含两个整数N和K。

(1 <= N, K <=100000)
 以下N行每行包含两个整数Hi和Wi。

(1 <= Hi, Wi <= 100000)
 输入保证每位小朋友至少能获得一块1x1的巧克力。


 输出
 输出切出的正方形巧克力最大可能的边长。


 样例输入
 2 10
 65
 56
 样例输出
 2
   
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],w[N];
bool check(int x)//x就是我们要找的最大的边长； 
{
	int num=0;//我们可以截取的块数； 
	for(int i=0;i=m)//如果截取的块数大于小朋友的人数； 
	{
		return true;
	}
	else
	{
		return false;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i>h[i]>>w[i];//长和宽； 
	}
	int l=1,r=1e5;//l=1是因为输入保证每位小朋友至少能获得一块1x1的巧克力
	while(l>1;
		if(check(mid))
		{
			l=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<
 
如果理解有误，请不吝赐教。

谢谢！
  					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/langs/564226.html

C++二分知识模板与例题

发表评论

评论列表（0条）