首页 > 代码库 > 二分算法和三分算法
二分算法和三分算法
二分算法：
hdu1969 PIE
题意：f+1个人分n分pie，pie只能切开不能从组，也就是说每个人拿到的必须是一个整块，不能是多个碎块。要求每个人分的的大小一样。n份pie的大小不同。目标是求出没人可能吃到的最大大小V。
分析抽象：首先条件是必须够n个人吃，要求大小一样的情况下求最大的V。关系是随着V的增大，所能support的人越少。这里有一个非递增的关系。所以而已考虑二分法。问题对精度的要求是二分法使用的关键。要求保留4位小数，所以我们统一乘上1000000来计算。
#include<iostream>#include<cstdio>#include<cmath>#define PI acos(long double(-1))using namespace std;long long a[10000+1];long long low, high, mid, res;int N, F;bool judge(){ int num = 0; for(int i =0; i<N; i++) { num += a[i]/mid; } return num>=F+1;}int main(){ int T; long long t; int i; cin>>T; while(T-->0) { cin>>N>>F; long long max = 0; for(i=0; i<N; i++) { cin>>t; a[i] = t*t*PI*1000000; if(a[i]>max) max = a[i]; } low = 0; high = max; while(low<=high) { mid = (high + low)/2; if(judge()) { low = mid+1; res = mid; } else high = mid-1; } printf("%.4lf\n",(double)res/1000000); } return 0;}
总结：二分法竟然还可以这样使用，看来对于单调的关系，求满足某种关系的特定值问题都可以考虑二分法。
关于这个问题还有讨论点：
这是针对第一组测试数据画的图，图中的红点即为要求值。但是如果改变题目的意思，要求p=4时所对应的最小值，该怎么办呢。
其实这个问题就变成了二分搜索中求第一个目标值和最后一个目标值的问题了。
举例:6 7 8 8 8 9 10 这7个数的存在a[]中，分别写出求第一个8和最后一个8的算法代码；
求第一个：
1 l = 0, r = 6; 2 while(l<r) 3 { 4 mid = (l + r)/2; 5 if(a[mid]>=8) 6 r = mid - 1; 7 else 8 l = mid + 1; 9 }10 ans = l;
求最后一个：
l = 0, r = 6;while(l<r){ mid = (l + r)/2; if(a[mid]<=8) l = mid + 1; else r = mid - 1;}ans = r;
本题选用的是后者。
可见实际问题只要抽象成数学问题分析起来就单纯的多了。
三分算法：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。