求最大值最小

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int a[11451454],n,k;
bool check(int o){
	//据题意编写 
	return a[o]>=k;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=0,r=n+1;//r的值有时需更大
    //sort(a+1,a+n+1);
    while(r-l>1){
    	int m=(r+l)/2;
    	if(check(m))r=m;
		else l=m;
	}
	if(r==n+1)cout<<"Not found!";
	else cout<<r<<endl<<a[r];
}

输入

10 66
10 25 52 62 66 66 66 85 87 95

输出

5
66

求最小值最大

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int a[11451454],n,k;
bool check(int o){
	//据题意修改 
	return a[o]<=k;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=0,r=n+1;
    //sort(a+1,a+n+1);
    while(r-l>1){
    	int m=(r+l)/2;
    	if(check(m))l=m;
		else r=m;
	}
	if(l==0)cout<<"Not found!";
	else cout<<l<<endl<<a[l];
}

输入

10 66
10 25 52 62 66 66 66 85 87 95

输出

7
66

实数区间二分

#include<bits/stdc++.h>
using namespace std;
double a[11451454],n,k;
bool check(int o){
	//据题意编写 
	return a[o]>=k;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    double l=0,r=n+1;//r的值有时需更大
    //sort(a+1,a+n+1);
    while(abs(r-l)>0.001){//保留2位小数，据题意 
    	double m=(r+l)/2;
    	if(check(m))r=m;
		else l=m;
	}
	if(r==n+1)cout<<"Not found!";
	else cout<<(int)r<<endl<<a[(int)r];
	//最小值最大同上 
}

输入

5 1.08
1.01 1.04 1.06 1.09 1.11

输出

4
1.09

例题

营救

典型的求最大值最小,难点为 check( ) 里的内容.

输入

6 3
20 30 50 80 100 120

#include<bits/stdc++.h>
using namespace std;
#define int long long
const long long jk=10000000;
int a[jk],n,m,l,r;
bool sanb(int k){
	int f=1,t=1;
	int p[114514];
	memset(p,0,sizeof(p));
	int num=0;//计算是否超过mid 
	for(int i=1;i<=n;i++){
		if(num+a[i]>k){
			f++;
			num=a[i];
			p[t]=num;//存储答案 
			t++;
			if(f>m)return 0;
		}
		else num+=a[i];
	} 
	p[t]=num;
	t++;
	sort(p+1,p+1+t);//求最大值 
	return p[t]<=k;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	r+=a[i];
	}
	l=1;
	r*=2;//增大边界 
    while(r-l>1){
    	int mid=(r+l)/2;
    	if(sanb(mid))r=mid;
		else l=mid;
	}
	cout<<r;//最大值最小，输出右边界 
}