文章目录
关于二分答案的定势思维纠正关于01背包的错误理解关于vector和lower_bound的错误使用关于二分答案的定势思维纠正
以前有风险的做法,二分后才记录答案
while(l<r){ll mid=(l+r)>>1;if(check(mid)) {//ans=mid;r=mid;}else l=mid+1;}cout<<l<<endl;
正确做法,二分的时候就记录答案
ll ans=-1e9;//一个不可能的数字while(l<=r){ll mid=(l+r)>>1;if(check(mid)) {ans=mid;r=mid-1;}else l=mid+1;}if(ans==-1e9) ans=l;printf("%lld\n",ans);
验证例题
补充:只在二分记录答案也可能会出错,因为有的情况而分不出合法的情况,这种时候应该视题目要求取l或者r
例题验证
关于01背包的错误理解
题目链接
先放错误理解,这里的j应该遍历到0
关于vector和lower_bound的错误使用
原场景是:p数组里面存的是素数,然后我要找到小于等于n的最后一个素数的位置。lower_bound是查找大于等于n的第一个数,我是这样写的:
int p1=lower_bound(p.begin(),p.end(),n)-p.begin();if(p[p1]>n) p1--;
如果p数组中存在比n大的数,那么没问题,但是就是因为可能不存在,p1=p.size(), 本来应该p1=p1-1。 但是我的那个if语句判断不会报错也不会成立。这样就导致我wa了11次!
正确做法:
int p1=lower_bound(p.begin(),p.end(),n)-p.begin();if(p[p1]>n||p1>=p.size()) p1--;
原题链接