位运算思维导图

这就是一道典型的二分答案（最大的最小值）模板题

#include<bits/stdc++.h> using namespace std; int a[50005],L,n,m; int check(int x){ int past=a[1],cnt=0; for(int i=2;i<=n+2;i++){ if(a[i]-past>=x) past=a[i]; else cnt++; } return cnt; } int main(){ cin>>L>>n>>m; a[n+2]=L; a[1]=0; for(int i=2;i<=n+1;i++) scanf("%d",&a[i]); int l=1,mid,r=a[n+2]-a[1]; while(l<r){ mid=(l+r+1)/2; if(check(mid)<=m) l=mid; else r=mid-1; } cout<<l; return 0; }

这里的函数我们无法知道函数图像是怎么样的，有可能是上升，有可能是下降，还有可能是上升再下降再上升。所以我们只能根据题目给的条件，两个根之差一定大于1，并且画一下图便可知，有三种情况1.l与r的差大于1，这种情况下可能有解2.l与r代入方程之后值同号，这样有且可能有两个解3.l与r的差大于1且l与r代入方程后值同好，这一定无解

double check(double x){ return a*x*x*x+b*x*x+c*x+d; } void check1(double l,double r){ if(r-l<1&&check(l)*check(r)>0) return;//这种情况一定无解，所以返回 double mid=(l+r)/2; if(abs(check(mid)-0)<=0.001){//精度 printf("%.2lf ",mid); return ; } //分成两个部分继续找剩余解 check1(l,mid); check1(mid,r); }

做法与河中跳房子基本一致，只需要初始化一下就行

for(int i=1;i<=n;i++){ scanf("%d",&a[i]); maxn=max(a[i],maxn); minn=min(a[i],minn); } sort(a+1,a+1+n); int k=n-m; int l=1,r=maxn-minn+1,mid;

位与&

位或|

异或^