二分-补题

造海船

描述

明朝郑和下西洋，需要建造庞大的海船，需要足够的木料，因为那时候没有钢铁制造的船，现在有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余），用来制造船的部件。

当然，工匠希望得到的小段木头越长越好，这样可以让船更大一些不浪费木料，请求出 l 的最大值。

原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。

现在希望你能用现代科技可以帮助他们计算出来。

输入描述

第一行是两个正整数 n,k，分别表示原木的数量，需要得到的小段的数量。
接下来 n 行，每行一个正整数 Li，表示一根原木的长度。

输出描述

仅一行，即 l 的最大值。
如果连 1cm 长的小段都切不出来，输出 0。

样例输入 1

3 7
232
124
456

样例输出 1

114

提示

数据规模与约定
对于 100% 的数据，有 1≤n≤105，1≤k≤108，1≤Li≤10^8(i∈[1,n])。

题解

#include<iostream>
using namespace std;
#define LL long long
int n,k,l,r,mid,a[100860];
LL sum=0;

bool yvn (int x){
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=a[i]/x;
    }
    return ans>=k;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
    if(sum<k) cout<<"0"<<endl;
    else if (sum==k) cout<<"1"<<endl;
    else {
        l=0;
        r=sum/k;
        while(l<r){
            mid=(l+r+1)>>1;
            if(yvn(mid)) l=mid;
            else r=mid-1;
        }cout<<l<<endl;
    }
    return 0;
} 

寻找第一个1

题目描述

给定一个01序列，序列从左至右一开始是若干个0，接下来直到末尾是若干个1。求第一个1的下标；如果序列中没有1，那么输出-1。

注：使用二分法实现。

输入描述

输出描述

输出第一个1的下标；如果没有1，那么输出-1。

测试用例

样例1

输入

5
0 0 0 1 1

输出

3

解释

从左到右第一个1的下标是3

样例2

输入

5
0 0 0 0 0

输出

-1

解释

序列中没有1，因此输出-1

题解

只需要在二分模板的基础上稍加修改，当找到1的时候不让他结束，继续往左找，因为要找第一个1，不确定左边还有没有1，这里还需要定义一个标志位flag，如果找到1那么变为true，最后while循环结束只要看一下是不是true，不是的话说明没找到，输出-1就ok了。

#include<bits/stdc++.h>
using namespace std;
bool flag = false;
const int N = 1e6;
int A[N];

int BinarySearch(int *a,int len){
	int low = 0,high = len-1,mid;
	while(low<=high){
		mid = (low+high)/2;
		if(a[mid] == 1){
			high = mid-1;
			flag = true;
		}else{
			low = mid+1;
		}
	}
	return flag == true?high+1:-1;
}

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	cout << BinarySearch(A,n);
}

查找数字是否出现

描述

在一个升序序列中，查找给定值是否存在，如果存在输出YES，否则输出NO。

输入描述

第一行一个整数n，表示升序序列的长度（1<n≤107） 。
第二行包含n个整数，升序序列各元素。所有元素取值区间（0~1010）。
第三行一个整数m，表示要查询数值的个数（1<m<105）。
接下来m行，每行一个整数，表示要查找数字。查找数字取值（ 0~1010 ）。

输出描述

m行，每行YES或NO，如果存在输出YES，否则输出NO。保持输入顺序。

样例输入 1

5
1 1 3 6 1024
2
1000
6

样例输出 1

NO
YES

题解

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
int A[N];

int main() {
    int key,n,m,mid;
    cin >> n;
    for(int i = 0;i < n;i ++){
        cin >> A[i];
    }
    cin >> m;
    while(m--){
        cin >> key;
        int low = 0,high = n-1,flag;
        while(low <= high){
            mid = (low+high)/2,flag = 0;
            if(A[mid] == key) {
                cout << "YES" << endl;
                flag = 1;
                break;
            }else if(A[mid] > key) high =mid - 1;
            else low = mid+1;
        }
        if(!flag) cout << "NO" << endl;
    }
    return 0;
}

字典找数

描述

现有一字典，查找字典15到45页中，某一页的页码，用二分法快速翻至所需要页码，需要翻多少次？（中间值 mid = (最大值+最小值)/2）

输入描述

字典中某一页的页码n。（15≤n≤45）

输出描述

一个整数，表示查找的次数。

样例输入 1

18

样例输出 1

3

题解

#include<bits/stdc++.h>
using namespace std;
int main() {
	int low = 15,high = 45,mid,n,count = 0;
    cin >> n;
    while(low<=high){
        mid = (low+high)/2;
        if(mid == n) {
            count++;
            break;
        }else if(mid < n){
            low = mid + 1;
            count++;
        }else{
            high = mid - 1;
            count++;
        }
    }
    cout << count;
	return 0;
}

寻找第一个偶数

题目描述

给定一个正整数序列，序列从从只有一开始是若干个奇数，接下来直到末尾是若干个偶数。求第一个偶数的下标；如果序列中没有偶数，那么输出-1。

注：使用二分法实现。

输入描述

输出描述

输出第一个偶数的下标；如果没有偶数，那么输出-1。

样例1

输入

5
3 5 1 8 6

输出

3

解释

从左到右第一个偶数是8，下标是3

样例2

输入

5
3 5 1 7 3

输出

-1

解释

序列中没有偶数，因此输出-1

题解

#include<bits/stdc++.h>
using namespace std;
bool flag = false;
const int N = 1e6;
int A[N];

int BinarySearch(int *a,int len){
	int low = 0,high = len-1,mid;
	while(low<=high){
		mid = (low+high)/2;
		if(a[mid] % 2 == 0){
			high = mid-1;
			flag = true;
		}else{
			low = mid+1;
		}
	}
	return flag == true?high+1:-1;
}

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	cout << BinarySearch(A,n);
}