蓝桥杯备赛 Day8 二分

二分

1.要点

选取左闭右闭,[left,right]
(1)二分查找：有序数组，且无重复元素寻找目标值key

int left=0,right=n-1,res=-1;//未找到返回-1
while(left<=right){int mid=left+((right-left)>>1); //注意右边括号，+号优先于>>if(a[mid]==key){res=mid;break;}else if(a[mid]<key){ //key在现在区间右侧left=mid+1;}else{ //key在现在区间左侧right=mid-1;}
}

(2)二分答案:广义的有序,查找某种条件的最大(最小值)(最大值最小化和最小值最大化),三个条件:

1. 答案在一个固定区间内；
2. 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
3. 可行解对于区间满足一定的单调性。换言之，如果x是符合条件的，那么有x+1或者x-1也符合条件。（这样下来就满足了上面提到的单调性）

int left=0,right=-1;
while(left<=right){int mid=left+((right-left)>>1);if(check(mid)) right=mid-1; //这边以最大值最小化举例，如果mid符合条件，说明它至少不是最小的,还可以再缩小区间,且固定区间是单调递增的else left=mid+1;
}
cout<<left<<"\n"; //输出left,而不是right

2.例题

2022 青蛙过河(二分答案最大值最小化)

找最小的跳跃距离y，是单调的；将总的区间划分为多个长度为y的子区间，只要每个子区间高度和(前缀和)大于等于2x即可(寻找目标target y的判断条件),所以为一个二分问题，left=1,right=n，如果mid满足判断条件，说明不是最小的跳跃距离，缩小右边界，如果mid不满足判断条件，说明跳跃距离不够缩小左边界，最终找到的target=left(或者right-1)

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e5+10;
int a[N],prefix[N],n,x;bool check(int y){//是否满足任意长度为y的区间高度和大于等于2*x //任意区间从1开始，n-1-y+1结束for(int i=1;i<=n-y;i++){//[i,i+y-1]区间和 if(prefix[i+y-1]-prefix[i-1]<2*x)	return false;} return true;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>x;for(int i=1;i<=n-1;i++){cin>>a[i];prefix[i]=prefix[i-1]+a[i];} int left=1,right=n-1,res=0;//左闭右闭while(left<=right){int mid=left+((right-left)>>1);if(check(mid)){right=mid-1;//res=mid;}else	left=mid+1;} cout<<left;//cout<<res;return 0;
}

2023冶炼金属

不用二分(不是最小值最大化这种，因为x成立，x-1不一定成立，不是单调的)，就是多个集合取交集，Vmin=max(),Vmax=min()

2017分巧克力

注意；
(1)这题是最小值最大化，满足条件left=mid+1,所以最终输出left-1(永远比最终结果多一)或者right(可以看最后两种情况,left==right时,若mid满足条件,left=mid+1结束循环,若mid不满足条件,肯定比key多1,right=mid-1=key)

#include <bits/stdc++.h>using namespace std;
typedef pair<int,int> PII; //或者直接开两个数组
const int N=1e5+10;
PII p[N];
int n,k;bool check(int mid){int sum=0;for(int i=0;i<n;i++){sum+=(p[i].first/mid)*(p[i].second/mid);if(sum>=k)	return true;}return false;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=0;i<n;i++){cin>>p[i].first>>p[i].second;}int left=1,right=1e5,mid,max,res=0;while(left<=right){mid=left+((right-left)>>1);if(check(mid)){left=mid+1;//res=mid;}else	right=mid-1;}cout<<right;//cout<<res;return 0;
}

2022技能升级

学习:
(1)暴力用max_element()函数获取地址,int pos=max_element-a获取索引可得40分，换成优先队列priority_queue可得60分
(2)满分为二分答案思想，但跟之前不一样，不是题目问什么就是寻找什么目标值，而要转换一下,寻找到一个能下降到的最低攻击力x,使得大于x的攻击力下降次数和<m次，x+1肯定也成立，所以为最大值最小化,得到x后可以得到下降次数,进而用等差数列得到大于x的攻击力和，再加上剩余次数*x即可
(3)加法和乘法时刻要想到显示转换为long long

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,a[N],b[N],x;bool check(int x){ll cnt=0;for(int i=0;i<n;i++){if(a[i]>x){cnt+= ceil((double)(a[i]-x)/b[i]); //攻击力下降到x的总次数，向上取整 if(cnt>m)	return false;		}}return true;
}ll sum(int a,int cnt,int b){ //a:首项,cnt:项数, b:差,d:末项 int d=a-b*(cnt-1);ll res=(ll)(a+d)*cnt>>1; //记得显示转换return res;
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i]>>b[i];}int left=0,right=1e6;while(left<=right){int mid=left+((right-left)>>1);if(check(mid)){right=mid-1;x=mid;}else	left=mid+1;}//x=left; //最后赋值或者在if里面赋值都一样ll res=0,cnt=0;for(int i=0;i<n;i++){if(a[i]>x){ll now=ceil((double)(a[i]-x)/b[i]);cnt+=now;res+=sum(a[i],now,b[i]); //等差数列求和算攻击力和 }}res+=(ll)(m-cnt)*x;//显示转换cout<<res;return 0;
}