1.题目描述:点击打开链接
2.解题思路:本题还是利用二分搜索解决,设函数ok(x)表示是否可以让每个人分到一块面积为x的派,然后进行二分搜索即可。
3.代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; int n, f; const double pi=acos(-1); #define N 10000+10 double d[N]; bool check(double x) { int sum = 0; for (int i = 0; i < n; i++) { int m = floor(d[i] / x); sum += m; } if (sum >= f + 1)return true; else return false; } int main() { //freopen("t.txt", "r", stdin); int T; cin >> T; while (T--) { scanf("%d%d", &n, &f); double maxd = -1; for (int i = 0; i < n; i++) { int r; cin >> r; d[i] = pi*r*r; maxd = max(maxd, d[i]); } double L = 0, R = maxd; double eps = 1e-5; while (R - L>eps) { double m = L + (R - L) / 2; if (check(m))L = m; else R = m; } printf("%.4lf\n", L); } return 0; }