这题写了那么多遍,要被边界问题整吐了
边界问题
首先这题要求的结果必须是最大值,那么我们就要使我的的结果向最大值靠近
那么问题来了我们是使用 if(test(mid)) r=mid;else l=mid
还是if(test(mid)) l=mid+1;else r =mid
还是if(test(mid)) l=mid; else r=mid-1
呢
-
首先不用多想,在l<r的循环前提下,第一种明显是不适合的,因为l一直等于mid且mid一直等于l,会陷入死循环;
-
那么第二种呢?假设第mid个可以满足切下的巧克力数,第r个不能满足,且第mid+1个也不满足,所以第二个代码就很巧妙的将左边界变成了mid+1,所以最后结果就是l-1;
-
第三种,当l=3,r=4时,且3满足条件,之后就会陷入死循环,所以我们的中间值要向上取整,不能用mid=l+r>>1,要使用mid=l+(r-l+1>>1);
具体的边界分析就是这样,我的处理方式选择的是第三种
C++代码
#include<iostream>
using namespace std;
const int N=1e5+10;
struct juxin{
int l,r;
}ju[N];
int f[N],v[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>ju[i].l>>ju[i].r;
//二分
int l=0,r=1e5,mid;
while(l<r)
{
mid =l+(r-l+1>>1);//向上取整
int cnt=0;
for(int i=1;i<=n;i++)
{
if(mid<=ju[i].l&&mid<=ju[i].r)
{
f[i]=(ju[i].l/mid)*(ju[i].r/mid);
cnt+=f[i];
}
}
//边界缩短
if(cnt>=m) l=mid;
else r=mid-1;
}
cout<<r<<endl;
return 0;
}