题目来源于学校oj(刷一部分比较简单的题)
模板题(但在A-B数对题里面改进了模板)
http://www.mangata.ltd/p/P1190
#include<iostream>
#include<algorithm>//含有sort函数，快速排序
using namespace std;
const int N=1e6+5;
int f[N],n;
int check(int x){
int l=0,r=n-1;
while(l<=r){//终止条件
int mid=(l+r)/2;
if(x>f[mid]) l=mid+1;
else r=mid-1;
}
if(f[l]==x) return l+1;//数组下标从0取，因此加一
else return -1;
}
int main(){
int m;
cin>>n>>m;
for(int i=0;i<n;++i){
cin>>f[i];
}
sort(f,f+n);//排序
while(m--){
int q;
cin>>q;
cout<<check(q)<<" ";
}
return 0;
}
A-B数对(这里面的模板感觉更好用)
http://www.mangata.ltd/p/P1191
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+5;
int f[N],n;
long long ans=0;
int checkleft(int x){//查询第一个出现目标数字的位置
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(x>f[mid]) l=mid;
else r=mid;
}
if(f[r]==x) return r;
else return -1;
}
int checkright(int x){//查询最后一个出现目标数字的位置
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(x>=f[mid]) l=mid;
else r=mid;
}
if(f[l]==x) return l;
else return -1;
}
int main(){
int c;
cin>>n>>c;
for(int i=0;i<n;++i){
cin>>f[i];
}
sort(f,f+n);
for(int i=0;i<n;++i){
int k=0;
k=f[i]+c;//b+c=a 也就是说此时只需要查找有没有a=k就行了
if(checkleft(k)!=-1){
ans=ans+checkright(k)-checkleft(k)+1;
}
}
cout<<ans;
return 0;
}
烦恼的高考志愿
比较容易
http://www.mangata.ltd/p/P1192
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+5;
int f[N],m;
int searchk(int x){//返回第一个大于查找值的数字的位置
int l=-1,r=m;
while(l+1<r){
int mid=(l+r)/2;
if(x>f[mid]) l=mid;
else r=mid;
}
return r;
}
int main(){
int n;
cin>>m>>n;
for(int i=0;i<m;++i){
cin>>f[i];//学校
}
sort(f,f+m);
long long ans=0;
while(n--){
int k;
cin>>k;
ans=ans+min(f[searchk(k)]-k,k-f[searchk(k)-1]);
}
cout<<ans;
return 0;
}
木材加工
乍一看没思路，思考了许久看了下以前自己的答案，捣鼓了一会儿写出来了
http://www.mangata.ltd/p/P1193
#include<iostream>
using namespace std;
const int N=1e6+5;
int f[N],k,n,sum=0,l=0,r;
bool check(int x){
int g=0;//存放砍了多少段
for(int i=0;i<n;++i){
g+=f[i]/x;//计算每个数千能砍多少截，并且相加
}
return g>=k;//如果能看出来那说明没问题
}
int checkplus(){
while(l+1<r){
int mid=(l+r)/2;
if(check(mid)) l=mid+1;
else r=mid-1;
}
return r;//返回的就是最大值,返回l的话会出现可切成1cm一段的情况为0
}
int main(){
cin>>n>>k;
for(int i=0;i<n;++i){
cin>>f[i];
sum+=f[i];
}
r=sum/k;//这是右边界
cout<<checkplus();
return 0;
}
杯子
万万没想到被二分的结束条件整错了，还找了好久
http://42.193.50.191/p/P1194
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define PI acos(-1)
double r1,R,h,v;
bool checkplus(double H,double R1){
double V= (1.0/3.0)*PI*H*(R1*R1+r1*r1+R1*r1);
if(V<=v) return true;//如果求出来的体积小了就要让左边变大
return false;
}
double check(double l,double r){
while(l+0.0000001<r){//最开始这里用的l+1<r找半天没发现问题
double mid=(l+r)/2.0,R1;
R1=r1+mid*(R-r1)/h;//由画图几何知识求解,R1为某高度下的上底半径
if(checkplus(mid,R1)) l=mid+0.0000001;
else r=mid-0.0000001;
}
return l;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>r1>>R>>h>>v;
printf("%.6lf",check(0,h));
}
return 0;
}
二分强化
http://42.193.50.191/p/P1195
会有个警告就是findplus函数里面不一定会返回一个值，但是对本题的解答没影响
#include<iostream>
using namespace std;
const int N=1e5+5;
int f[N],n,y;
int find0(int x){//数字最大下标
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(f[mid]>x) r=mid;
else l=mid;
}
if(x==f[l]) return l;
else return -1;
}
int find1(int x){
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(f[mid]<x) l=mid;
else r=mid;
}
if(f[r]==x) return r;
else return -1;
}
int find2(int x,int y){
return find0(y)-find1(x)+1;
}
int find3(int x){
if(find0(x)!=-1) return f[find0(x)+1];
return -1;
}
int find4(int x){
if(find1(x)!=-1) return f[find1(x)-1];
return -1;
}
int findplus(int q,int k){
if(q==0) find0(k);
else if(q==1) find1(k);
else if(q==2) find2(k,y);
else if(q==3) find3(k);
else if(q==4) find4(k);
}
int main(){
cin>>n;
for(int i=0;i<n;++i){
cin>>f[i];
}
int m;
cin>>m;
while(m--){
int q,k;
cin>>q>>k;
if(q==2) cin>>y;
int ans=findplus(q,k);
cout<<ans<<endl;
}
return 0;
}
小X算排名
#include<iostream>
using namespace std;
const int N=1e5+5;
int f[N];
int b[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=0;i<n;++i){
cin>>f[i];
b[f[i]]++;
}
for(int i=N-2;i>=0;--i){
b[i]+=b[i+1];//每一项相当于计算了包含自身的总人数
}
for(int i=0;i<n;++i){
cout<<b[f[i]+1]+1<<endl;
}
return 0;
}
差不多二分暂时刷这些了，等刷完一轮再刷后面的二分题
标签：二分,return,int,mid,cin,while,include,部分,模板 From： https://www.cnblogs.com/whynot-ne/p/17098266.html