目录
一. 二分
会二分首先得会二分模板吧
1. 二分模板
typedef long long LL; //long long 简写
LL l = 左边界，LL r = 右边界 //左右边界需自己读题分辨
while(l + 1 < r)
{
LL mid = (l + r )>>1; //'>>1'表示除2，与'/2'一样，只是比单纯除以2要快点
if(check(mid))(r or l) = mid; //左边满足条件，l = mid；
else (l or r) = mid; //右边满足条件，r = mid；
}
2. 什么情况下能用到二分？（时间复杂度是O(logn)）
一般用for循环遍历WA的题，可尝试用二分，说不定AC了呢！！
1.在一个有序数组中，找某个数是否存在
2.在一个有序数组中，找>=某个数最左侧的位置
3.局部最小值的问题
3. 二分使用方法
- 套模板
- 2.确定返回值（答案）是l or r；
- 是 l 就是 l = mid，是 r 就是 r = mid；
- 通过答案的范围来确定边界
- 写check
- AC
4. 例题(注重理解！！！)
- P1024 [NOIP2001 提高组] 一元三次方程求解
题目链接：https://www.luogu.com.cn/problem/P1024
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double a,b,c,d;
int ans=0;
double f(double x)
{
return a*x*x*x+b*x*x+c*x+d;// 计算一元三次方程的值
}
int main(){
scanf("%lf %lf %lf %lf",&a,&b,&c,&d);
for(int i=-100;i<100;i++){
double l=i,r=i+1;// 找到左边界与右边界
if(!f(l)){// 如果有满足f(x)=0的情况就输出
printf("%.2lf ",l);
ans++;
}
if(f(l)*f(r)<0){// 判断零点条件
while(l+0.001<r){
double mid=(l+r)/2;// 更新条件
if(f(mid)*f(r)<=0){
l=mid;// 左边界小了
}
else{
r=mid;// 右边界大了
}
}
printf("%.2lf ",r);
ans++;
}
if(ans==3)break;// 只需从小到大输出满足条件的三个
}
return 0;
}
- 木材加工
题目链接：https://www.luogu.com.cn/problem/P2440
题解：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=2e6+5;//注意范围
int n,k,x[maxn];
int check(ll mid)
{
int cnt=0;//用来记录所切木头根数
for(int i=0;i<n;i++){
cnt+=x[i]/mid;//计算能切多少根
}
if(cnt>=k)return 1;//如果能满足k段木头返回真
else return 0;//否则假
}
int main()
{
cin>>n>>k;//读入n根木头和要得到的k段木头
for(int i=0;i<n;i++){
cin>>x[i];//读入每根木头的长度
}
ll l = 0,r = 1e8+1;//模板套用，最小边界为0（一根也切不出来），最大边界为题目所给定的
while(l + 1 < r){
ll mid = (l + r) >> 1;
if(check(mid)) l = mid;//如果mid为真，说明所切的木头还可以更大
else r = mid;//否则就减小所切长度
}
cout<<l<<endl;//最后输出正确结果
}
- 【深基13.例1】查找
题目链接：https://www.luogu.com.cn/problem/P2249
题解：
二.双指针
相比二分，双指针我觉得比二分好理解，直接上题！
Eating Candies
题目链接：https://www.luogu.com.cn/problem/CF1669F
题解：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=2e6+5;
int a[maxn],n;
int main()
{
int t;
cin>>t;//测试样例数
while(t--){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];//读入每组数据
}
ll l=0,r=n-1;//左值为数组下标第一位，右值为数组下标最后一位
int cnt=0,Alice=0,Bob=0,candy=0;//Alice，Bob记录各自吃到的糖果，candy记录一共吃的糖果数量
while(l<=r){
if(Alice<=Bob){
Alice+=a[l];//从Alice开始吃
l++;//吃一颗，下标往右移
candy++;
}
else{
Bob+=a[r];//糖果重量Alice>Bob时，Bob开始吃
r--;//吃一颗，下标左移
candy++;
}
if(Alice==Bob){
cnt=max(cnt,candy);//当糖果重量相等时，就比较一次糖果数谁多，取最多糖果数
}
}
cout<<cnt<<endl;//最终输出最多糖果数
}
}
标签：二分,int,ll,mid,long,模板,指针 From： https://www.cnblogs.com/yishujia/p/17895490.html完结！！！