造海船

描述

明朝郑和下西洋，需要建造庞大的海船，需要足够的木料，因为那时候没有钢铁制造的船，现在有 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);
}