首页 > 代码库 > poj 2456 二分法 最大化最小值
poj 2456 二分法 最大化最小值
题目:http://poj.org/problem?id=2456
重新练习下二分法,发现还是手速不够
从这道题学到一下几点:
1、线性分几段的方法,看我的Judge()代码;
2、二分的while()最终打印的是down,而不是mid(我代码里写的是ans),或者up,
这么想:跳出循环的时候,假设while里的判断,Judge(ans)==1,那么down是正确解,up不是
Judge(ans)==0,那么ans跟up都不是正确解
综上,打印down才能输出正确解
3、调了好一会二才发现的bug:Judge函数里,if(cnt<c-1)return 0; 注意,cnt==1已经可以有两个牛仓了!!!
贴代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 100000+10; int n,c; int dis[MAXN]; int Judge(int s) { int cnt=0,last=0,now=0; while(now<n) { //////////////////////////// //printf("last=%d now=%d cnt=%d s=%d\n",last,now,cnt,s); //////////////////////////// now=last+1; while(now<n && dis[now]-dis[last]<s)now++; if(now<n) { cnt++; last = now; } } if(cnt<c-1)return 0;/* 此处二逼过*/ else return 1; } int main() { while(scanf("%d%d",&n,&c)!=EOF) { for(int i=0;i<n;i++) scanf("%d",&dis[i]); sort(dis,dis+n); int maxdis=dis[n-1]-dis[0]; int up=maxdis+1,down=0,ans=up;// //printf("************%d\n",up); while(up-down>1) { ans=(up+down)/2; if(Judge(ans))down=ans; else up=ans; } printf("%d\n",down);//??ans? } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。