題干：

My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.?

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.?

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.

Input

One line with a positive integer: the number of test cases. Then for each test case:

• One line with two integers N and F with 1 ≤ N, F ≤ 10 000: the number of pies and the number of friends.
• One line with N integers ri with 1 ≤ ri ≤ 10 000: the radii of the pies.

Output

For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10??3.

Sample Input

3 3 3 4 3 3 1 24 5 10 5 1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327 3.1416 50.2655

解題報(bào)告：

? ? 餡餅的面積排序然后從0到最大的面積二分尋找滿足的值

ac代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<cmath>using namespace std; const double PI = acos(-1.0); const double eps = 1e-6; double a[10000 + 5]; int n,f,t; bool cmp(const double & a,const double & b) {return a>b; } double mid; bool ok() {int sum=0;for(int i = 0; i<n; i++) {sum+=(int)(a[i] / mid);}return sum >= f ; }int main() { // freopen("in.txt","r",stdin);scanf("%d",&t);while(t--) {scanf("%d %d",&n,&f);f++;for(int i = 0; i<n; i++) {scanf("%lf",&a[i]);a[i]=a[i]*a[i]*PI;}sort(a,a+n,cmp);if(n>f) n=f;//如果人數(shù)沒有蛋糕數(shù)多，那就取最大的那幾個蛋糕。 // sort(a,a+n); // double l=a[0]; // double r=a[n-1];double l = 0;double r = a[0];while(r-l>=eps) {mid = (l+r )/2;if(ok() ) l=mid;else r=mid;}printf("%.4f\n",l);}return 0 ; }

總結(jié)：

? ? ? ?1. ok函數(shù)中for循環(huán)內(nèi)的那一層判斷，完全可以寫成（嗎？）（好像不太行 但是為什么？）

bool ok() {int sum=0;for(int i = 0; i<n; i++) {int tmp = a[i];while(tmp>=mid) {sum++;tmp-=mid;} }return sum >= f ;}

即：依次遞減總是可以優(yōu)化成除法！因?yàn)槭蔷€性結(jié)構(gòu)，所以可以跳躍

? ? ? 2.還是ok函數(shù)中，加括號！！ 不然出來的全是整數(shù)！ 優(yōu)先級問題！

? ? ? 3.最后的輸出 ?mid 也能ac，但是不太符合原題的意思，所以最好還是輸出l。

? ? ? 4.這件事情告訴我們 二分不僅能查找量（可用stl），還能尋值

?

總結(jié)

以上是生活随笔為你收集整理的**【POJ - 3122】 Pie（二分寻值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。