poj 1434 --Fill the Cisterns!(기 하
Fill the Cisterns!
Time Limit: 5000MS
Memory Limit: 10000K
Total Submissions: 1806
Accepted: 653
DescriptionDuring the next century certain regions on earth will experience severe water shortages. The old town of Uqbar has already started to prepare itself for the worst. Recently they created a network of pipes connecting the cisterns that distribute water in each neighbourhood, making it easier to fill them at once from a single source of water. But in case of water shortage the cisterns above a certain level will be empty since the water will to the cisterns below.
You have been asked to write a program to compute the level to which cisterns will be lled with a certain volume of water, given the dimensions and position of each cistern. To simplify we will neglect the volume of water in the pipes.TaskWrite a program which for each data set:reads the description of cisterns and the volume of water,computes the level to which the cisterns will be filled with the given amount of water,writes the result.
Input
The first line of the input contains the number of data sets k, 1 <= k <= 30. The data sets follow.
The first line of each data set contains one integer n, the number of cisterns, 1 <= n <= 50 000. Each of the following n lines consists of 4 nonnegative integers, separated by single spaces: b, h, w, d - the base level of the cistern, its height, width and depth in meters, respectively. The integers satisfy 0 <= b <= 10^6 and 1 <= h * w * d <= 40 000. The last line of the data set contains an integer V - the volume of water in cubic meters to be injected into the network. Integer V satisfies 1 <= V <= 2 * 10^9.
Output
The output should consist of exactly d lines, one line for each data set.
Line i, 1 <= i <= d, should contain the level that the water will reach, in meters, rounded up to two fractional digits, or the word 'OVERFLOW', if the volume of water exceeds the total capacity of the cisterns.
Sample Input
3
2
0 1 1 1
2 1 1 1
1
4
11 7 5 1
15 6 2 2
5 8 5 1
19 4 8 1
132
4
11 7 5 1
15 6 2 2
5 8 5 1
19 4 8 1
78
Sample Output
1.00
OVERFLOW
17.00
제목:N 개의 싱 크 대 를 드 리 겠 습 니 다.싱 크 대 는 높이 가 다 르 고 용량 도 다 릅 니 다.지금 은 일정한 수량 V 를 드 리 겠 습 니 다.이 물 을 이 싱 크 대 뒤에 부 은 물 을 높이 로 올 려 주세요.
해법:이분.
1.싱 크 홀 의 유효 구간,즉 맨 아래 싱 크 홀 의 아래쪽 LOW 와 싱 크 홀 중 가장 높 은 높이 HIGH,즉 2 분 을 진행 할 구간 을 먼저 찾아낸다.
2.2 분 구 간 에 한 개의 선 을 확정 하고 이 선 이 마침 양보 할 수 있 는 수량 V 가 이 높이 까지 올 랐 는 지 테스트 한다.
3.얻 은 구분 선 MID 가 이 선 이하 의 수량 에 딱 맞 게 V 라 고 해도 꼭 정 해 는 아니다.
이 선 이 연못 의 중간 부분 을 그 어 본 적 이 없 을 수도 있 기 때문이다.예 를 들 어 1.그 어 진 선 이 1.5 일 때 도 이 조건 을 만족 시 킬 수 있다.
그 러 니 이 경우 이 선 을 HIGH 로 삼 아 계속 2 점 을 찾 아야 합 니 다.
또한 정밀도 제 어 는 반드시<0.001,나 는 0.002WA 를 시도 해 야 한다.
코드:
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define min(a,b) a<b?a:b
struct cistren
{
int b,h,w,d,f;
}num[50010];
int sum,n;
double cal(double &line)
{
double result=0;
for(int i=0;i<n;i++)
{
if(line>num[i].b)
{
double t=min(line,num[i].f);
result+=(t-num[i].b)*num[i].w*num[i].d;
}
}
return result;
}
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int total=0;
double low=99999999,high=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&num[i].b,&num[i].h,&num[i].w,&num[i].d);
num[i].f=num[i].b+num[i].h;
total+=num[i].h*num[i].w*num[i].d;
if(num[i].b+num[i].h>high)
high=num[i].b+num[i].h;
if(num[i].b<low)
low=num[i].b;
}
scanf("%d",∑);
if(sum>total)
{
printf("OVERFLOW
");
}
else
{
double mid;
while(high-low>0.001)
{
mid=(low+high)/2.0;
double ans=cal(mid);
if(fabs(ans-sum)<=0.001)
{
for(i=0;i<n;i++)
{
if(mid>num[i].b&&num[i].f>mid)
break;
}
if(i<n)
break;
else
high=mid;
}
else if(ans>sum)
high=mid;
else
low=mid;
}
printf("%.2lf
",mid);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.