2 점 찾기 Problem 1003 Pie
간단 한 제목: N 개의 pie 가 있 습 니 다. F + 1 명 에 게 나 누 어 줍 니 다.각 pie 의 높이 는 1 이지 만 반경 은 반드시 같 지 않다.모든 사람 은 같은 부피 의 pie 로 나 누 어야 하지만, 모든 사람 은 하나의 pie 만 얻 을 수 있 을 뿐, 여러 조각 을 모 을 수 는 없다.일부분 을 낭비 할 수 있다.N, F, 각 pie 의 반지름 리 를 제시 하여 모든 사람 이 얻 을 수 있 는 pie 의 최대 부피 V 를 구 합 니 다.
문제 풀이 사고의 형성 과정: 한 사람 이 가장 큰 pie 의 부 피 를 나 눌 수 있 고 적어도 0 으로 나 눌 수 있 으 며 이분법 을 이용 하여 요 구 를 만족 시 키 는 모든 사람 이 얻 을 수 있 는 pie 의 최대 부피 V 를 구 할 수 있다.
소감: 처음에는 이분법 을 생각 하지 못 하고 다른 방법 을 사 용 했 습 니 다. WA 는 여러 번 고 쳤 지만 아무리 고 쳐 도 안 됩 니 다. 이분법 AC 를 사용 한 후에 곰 곰 이 생각해 보 니 처음에 알고리즘 에 심각 한 구멍 이 있 었 습 니 다.
코드 를 쓰기 전에 자신의 알고리즘 이 정확 한 지, 빈틈 이 있 는 지, 특히 일부 특수 하고 경계 상황 이 고려 되 지 않 은 지 곰 곰 이 생각 하고 확인 해 야 한다.자신의 알고리즘 이 틀 리 지 않 았 음 을 확인 한 후에 코드 를 쓰기 시작 합 니 다.
코드:
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
#define pi acos(-1.0) //acos： 。 cosπ=-1， -1 π。 。
bool cmp(double a,double b)
{
return a>b;
}
int main()
{
int n;
//freopen("1.txt","r",stdin);
cin>>n;
while(n--)
{
int N,F;
cin>>N>>F;
++F;
vector <double> ri;
for(int i=0;i<N;++i){
int temp1;
scanf("%d",&temp1);
double temp2=pi*pow(temp1,2);
ri.push_back(temp2);// pie 。
}
sort(ri.begin(),ri.end(),cmp);
double l=0,r=ri[0]; //ri[0] pie 。
double mid=(l+r)/2;
while(r-l>1e-7){ // 。
int total=0;
for(int i=0;i<N;++i)
total+=(int)(ri[i]/mid);// ！！ ！
if(total>=F)
l=mid;
else
r=mid;
mid=(l+r)/2;
}
printf("%.4lf
",mid);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Java 이분 검색 알고리즘 실례 분석 실현본고는 자바 구현 이분 검색 알고리즘을 실례로 다루고 있다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적으로 다음과 같습니다. 1. 전제: 2분 찾기의 전제는 찾아야 할 수조가 이미 정렬되어 있어야 한다는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
