模板
找到第一个大于5的元素
bool isBlue(int x){
if(x<=5) return true;
else return false;
}
int l=1, r=9;
while(l+1!=r){
int mid = (l+r)/2;
if(isBlue(q[mid])){
l=mid;
}else{
r=mid;
}
}
return r;
|
找到最后一个小于等于5的元素的位置(下标)
bool isBlude(int x){
if(x<=5) return true;
else return false;
}
int l=-1, r=8;
while(l+1!=r){
int mid = (l+r)>>1;
if(isBlue(q[mid])){
l=mid;
}else{
r=mid;
}
}
return l;
|
数的范围
给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 nn 和 qq，表示数组长度和询问个数。
第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。
输出格式
共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n, q;
int arr[N];
bool isBlue1(int num, int x){
if(num<x) return true;
else return false;
}
int binary_search1(int q[], int len, int x){
int l=-1, r=len;
while(l+1<r){
int mid=l+r>>1;
if(isBlue1(q[mid], x)) l=mid;
else r=mid;
}
if(q[r]==x) return r;
else return -1;
}
bool isBlue2(int num, int x){
if(num<=x) return true;
else return false;
}
int binary_search2(int q[], int len, int x){
int l=-1, r=len;
while(l+1<r){
int mid=l+r>>1;
if(isBlue2(q[mid], x)) l=mid;
else r=mid;
}
if(q[l]==x) return l;
else return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=0; i<n; i++){
cin>>arr[i];
}
while(q--){
int x;
cin>>x;
int res1=binary_search1(arr, n, x);
int res2=binary_search2(arr, n, x);
cout<<res1<<" "<<res2<<endl;
}
return 0;
}
|
数的三次方根
给定一个浮点数 nn，求它的三次方根。
输入格式
共一行，包含一个浮点数 nn。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 66 位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
double n;
bool check(double x){
if(x*x*x<=n){
return true;
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
double l=-100, r=100;
while(r-l>1e-8){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}
cout<<fixed<<setprecision(6)<<l<<endl;
return 0;
}
|
查找
题目描述
输入 n 个不超过 109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,a**n，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
输入输出样例
输入 #1复制
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
|
输出 #1复制
说明/提示
数据保证，1≤n≤106，0≤a**i,q≤109，1≤m≤105
本题输入输出量较大，请使用较快的 IO 方式。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int arr[N];
int n, m;
int binary_search(int x){
int l=0, r=n+1;
while(l+1<r){
int mid=l+r>>1;
if(arr[mid]<x){
l=mid;
}else{
r=mid;
}
}
if(arr[r]==x){
return r;
}else{
return -1;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int x;
for(int i=1; i<=n; i++){
cin>>arr[i];
}
for(int i=1; i<=m; i++){
cin>>x;
int res=binary_search(x);
cout<<res<<" ";
}
return 0;
}
|
数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×105，0≤a**i<230，1≤C<230。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
int q[N];
int n, c;
long long res;
int binary_search1(int x){
int l=-1, r=n;
while(l+1<r){
int mid=l+r>>1;
if(q[mid]<x){
l=mid;
}else{
r=mid;
}
}
if(q[r]==x) return r;
else return -1;
}
int binary_search2(int x){
int l=-1, r=n;
while(l+1<r){
int mid=l+r>>1;
if(q[mid]<=x){
l=mid;
}else{
r=mid;
}
}
if(q[l]==x) return l;
else return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>c;
for(int i=0; i<n; i++){
cin>>q[i];
}
sort(q, q+n);
int res1=0;
int res2=0;
for(int i=0; i<n; i++){
int x=q[i]+c;
res1=binary_search1(x);
if(res1!=-1){
res2=binary_search2(x);
}else{
continue;
}
res=res+res2-res1+1;
}
cout<<res;
return 0;
}
|
EKO / 砍树
题目描述
伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 H，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。
输入格式
第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。
第 2 行 N 个整数表示每棵树的高度。
输出格式
1 个整数，表示锯片的最高高度。
输入输出样例
输入 #1复制
输出 #1复制
输入 #2复制
输出 #2复制
说明/提示
对于 100% 的测试数据，1≤N≤106，1≤M≤2×109，树的高度 ≤4×105，所有树的高度总和 >M。
数据尽量开long long typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n, m;
int q[N];
int binary_search(int l, int r){
bool flag=false;
while(l+1<r){
long long sum=0;
int mid=l+r>>1;
for(int i=0; i<n; i++){
if(q[i]>mid){
sum+=q[i]-mid;
}
}
if(sum>=m){
l=mid;
}else{
r=mid;
}
}
return l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0; i<n; i++){
cin>>q[i];
}
sort(q, q+n);
int min=q[0], max=q[n-1];
int res=binary_search(0, q[n-1]);
cout<<res;
return 0;
}
|
木材加工
题目背景
要保护环境
题目描述
木材厂有 n 根原木，现在想把这些木头切割成 k 段长度均为 l 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11 和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。
输入格式
第一行是两个正整数 n,k，分别表示原木的数量，需要得到的小段的数量。
接下来 n 行，每行一个正整数 L**i，表示一根原木的长度。
输出格式
仅一行，即 l 的最大值。
如果连 1cm 长的小段都切不出来，输出 0。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
数据规模与约定
对于 100% 的数据，有 1≤n≤105，1≤k≤108，1≤L**i≤108(i∈[1,n])。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e8;
ll n,k;
ll res;
ll q[N];
ll binary_search(ll l, ll r){
while(l+1<r){
ll sum=0;
ll mid=(l+r)/2;
for(int i=0; i<n; i++){
sum+=q[i]/mid;
}
if(sum>=k){
l=mid;
}else{
r=mid;
}
}
return l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=0; i<n; i++){
cin>>q[i];
}
sort(q, q+n);
ll max=q[n-1];
res=binary_search(0, max);
cout<<res<<endl;
return 0;
}
|
跳石头
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。
接下来 N 行，每行一个整数，第 i 行的整数 D**i(0<D**i<L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
输入输出样例 1 说明
将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。
数据规模与约定
对于 20%的数据，0≤M≤N≤10。
对于 50% 的数据，0≤M≤N≤100。
对于 100% 的数据，0≤M≤N≤50000,1≤L≤109。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=50010;
ll L, n, m;
ll q[N]={0};
ll res;
bool check(ll x){
ll i=0, cnt=0, now=0;
while(i<n+1){
i++;
if(q[i]-q[now]<x){
cnt++;
}else{
now=i;
}
}
if(cnt<=m) return true;
else return false;
}
ll binary_search(ll l, ll r){
while(l+1<r){
ll mid=l+r>>1;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}
return l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>L>>n>>m;
for(int i=1; i<=n; i++){
cin>>q[i];
}
q[n+1]=L;
int l=0, r=L;
res=binary_search(0, L);
if(check(res+1)){
cout<<res+1<<endl;
}else{
cout<<res<<endl;
}
return 0;
}
|
题目背景
B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。
题目描述
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
输入格式
第 1 行包括三个数 L,N,K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 2 行包括递增排列的 N 个整数，分别表示原有的 N 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 [0,L] 内。
输出格式
输出 1 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 50 或 51 个单位距离处，这样能达到最小的空旷指数 51。
50% 的数据中，2≤N≤100，0≤K≤100。
100% 的数据中，2≤N≤100000, 0≤K≤100000。
100% 的数据中，0<L≤10000000。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
ll q[N], s[N], res;
ll L, n , k;
bool check(ll x){
ll sum=0, cnt=0, i=0;
while(i<=n+1){
sum=s[i];
while(sum>x){
cnt++;
sum=sum-x;
}
i++;
}
if(cnt<=k) return true;
else return false;
}
ll binary_search(ll l, ll r){
while(l+1<r){
ll mid=l+r>>1;
if(check(mid)){
r=mid;
}else{
l=mid;
}
}
return r;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>L>>n>>k;
for(int i=1; i<=n; i++){
cin>>q[i];
}
q[0]=0, q[n+1]=L;
for(int i=1; i<=n+1; i++){
s[i]=q[i]-q[i-1];
}
ll l=0, r=L;
res=binary_search(l, L);
if(check(res-1)){
cout<<--res<<endl;
}else{
cout<<res;
}
return 0;
}
|
