二分查找
关注
分享
扫一扫
文章平均质量分 76
happy_lcj
nothing
展开
-
poj 2728 Desert King (最优比率生成树)
题意：有n个村庄，给出每个村庄的坐标和海拔，benifit为两点之间的水平距离，cost为两点的高度差，现要求一棵树使得 cost / benift 最小，即求一个最优比例生成树分析：01规划的应用设x[i]等于1或0, 表示边取或者不取则所求的比率 rate = ∑(cost[i] * x[i]) / ∑(benifit[i] * x[i])原创 2015-01-29 16:36:43 · 887 阅读 · 0 评论 -
poj 2976 Dropping tests (01规划，二分查找)
链接:poj 2976题意：给定n和k,a1,a2...an和b1，b2...bn求扔掉k组数ai,bi 后,下面式子的最大值为多少分析：01规划的基本应用假设最大值为x可得： 100*sigma(a[i])/sigma(b[i])=x----> 100*sigma(a[i])-x*sigma(b[i])=0原创 2015-01-29 16:00:48 · 1041 阅读 · 0 评论 -
poj 1905 Expanding Rods (二分查找)
链接：poj 1905截取自某大牛的blog,详情请关注：链接：Enumz题意：一根两端固定在两面墙上的杆长度为L，受热弯曲后变弯曲，长度L′=（1+nc)*L 求前后两个状态的杆的中点位置的距离分析：设L′对应的半径为r，弧长为2α，要求的距离为x原创 2015-01-28 17:10:35 · 866 阅读 · 0 评论 -
poj 3122 Pie (二分查找)
题意：我生日派对时，准备了n个圆柱形的pie,半径比一定相同，但高都为1，邀请了f个朋友，加上自己一共f+1人，需要将n个pie分给f+1个人要求：每个人分得的pie尺寸要一样大，并且同一个人所分的pie要是从同一个pie上得到的，n个pie分完后可以有剩余求：每个人最多可以分多少原创 2015-01-28 16:37:21 · 1868 阅读 · 0 评论