首页 > 代码库 > 【hoj】2651 pie 二分查找
【hoj】2651 pie 二分查找
二分查找是一个很基本的算法,针对的是有序的数列,通过中间值的大小来判断接下来查找的是左半段还是右半段,直到中间值的大小等于要找到的数时或者中间值满足一定的条件就返回,所以当有些问题要求在一定范围内找到一个满足一些约束的值时就可以用二分查找,时间复杂度O(log n);
题目:http://acm.hit.edu.cn/hoj/problem/view?id=2651
因为题目有精度要求,对于浮点数小数点部分会有一定误差,所以可以选择将这些有小数部分的数值扩大e6倍,因为题目要求精确到e-3,之后结果在按照要求缩小就行
#include <iostream> #include <cstdio> #include <cmath> #define pi 3.14159265358979 #define MAX 10010 using namespace std; long long size[MAX]; int c,n,f; bool judge(long long x) { long long m = 0; for(int i = 0;i < n;i++){ m += size[i] / x; } return m >= f; } int main() { long long high,mid,low,res; int a; cin>>c; while(c --){ cin>>n>>f; f += 1; low = 0; high = 0; res = 0; a = 0; for(int i = 0;i < n;i++){ cin>>a; size[i] = a*a*pi*1000000; high += size[i]; } while(low <= high){ mid = (low + high)/2; if(judge(mid)){ low = mid+1; res = mid; } else high = mid-1; } printf("%.4lf\n",(double)res/1000000); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。