예제 1.13파 UVa12097

1311 단어 이분 검색
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
", L); } return 0; }

좋은 웹페이지 즐겨찾기