Gym

题目：

The cascade of water slides has been installed in the park recently and it has to be tested. The cascade consists of some number of reservoirs, or “ponds” for short, which are linked into a single sequence connected by water slides. Visitors are expected to start the journey in the topmost pond, then to be washed into subsequent lower ponds, and finally end the journey in the last pond of the cascade, which is also the lowest pond of the cascade. The journey spans all ponds in the cascade.

To test the cascade, each pond has to be completely filled with water. Each pond is attached to a pipe with a valve which, when opened, pours water into the pond. The sizes and capacities of different ponds are different. Fortunately, at least the pipes and the valves are standardized. Therefore, the rate at which water is poured through the valve into a pond is the same for all ponds.

When a pond is filled, water overflows and continues to flow into the next pond. If that pond is also filled, water continues to the next subsequent pond, and so on, until it either reaches some pond which has not been completely filled yet, or it overflows the lowest pond and sinks in the drain at the bottom of the cascade. The time in which the overflowing water reaches the next pond is considered to be negligible. The test starts at time 0 with all ponds being empty. Then, all valves are opened simultaneously. The test stops and the valves are closed when all ponds are filled by water.

The pond capacities and valves flow rate are known, you have to determine the moment when the lowest pond starts to overflow and the first moment when all ponds are filled.

Input Specification：

There are more test cases. Each test case consists of two lines. The first line contains two integers N (1 ≤ N ≤ 10⁵ , 1 ≤ F ≤ 10⁹ ) separated by space. N is the number of ponds, F is the rate of water flow through each valve. We consider the flow to be expressed in litres per second. The second line contains a sequence of N integers Ci (1 ≤ Ci ≤ 10⁹ ) separated by spaces and representing the pond capacities expressed in litres. The sequence reflects the order of ponds from the topmost one to the lowest one.

Output Specification：

For each test case, print a single line with two numbers separated by space. The first number represents the time in which the lowest pond in the cascade starts to overflow. The second number represents the duration of the test. Both times should be printed in seconds and should be accurate within an absolute or relative error of 10^-6.

题意：

从上到下给出N个池塘，每个池塘都有水管与它相连，每个水管的流量都是flow，当上一层的池塘的水满了之后，该池塘剩余流入的水就会依次流入下边的池塘中，问最后一个池塘灌满的时间和全部池塘被灌满的时间。

思路：

贪心：

1、最后一个池塘中的水满了的情况分两种

（1）没有上边的水流下，自己就灌满了；

（2）有上边的水流下来，加上自己的满了；

所以最后一个池塘灌满的时间应该是后边m个池塘中的水灌满的最短时间（依次将后边1个，后边2个，，，池塘看成一个整体，依次求出灌满的时间）。

2、全部灌满的时间，前m个池塘灌满的时间的最大值（依次将前边的1个，前边的2个，，，池塘看成一个整体，依次求出灌满的时间）。

二分：

整体思路：对所有的池塘和最后一个池塘灌满的时间（double类型）直接进行二分枚举。

判断所有池塘灌满的条件注意：

（1）前m个（1<=m<=n）池塘 t 时刻流入的水的和小于前m个池塘的容量和的话，肯定是灌不满的。

（2）前m个（1<=m<=n）池塘 t 时刻流入的水的和已经大于所有池塘的总容量的话，当前已经灌满了。

贪心代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll c[maxn];

int main(){
    int N;
    ll flow;
    while(scanf("%d%lld",&N,&flow)!=EOF){
        for(int i = 1; i<=N; i++){
            scanf("%d",&c[i]);
        }
        double all_filled = -1e9,final_filled = 1e9;
        ll sum = 0;
        for(int i = N; i>=1; i--){//逆序寻找后m个池塘灌满时间的最小值
            sum+=c[i];
            final_filled = min(final_filled, 1.0*sum/((N-i+1)*flow));
        }
        sum = 0;
        for(int i = 1; i<=N; i++){//正序寻找前m个池塘灌满时间的最大值
            sum+=c[i];
            all_filled = max(all_filled, 1.0*sum/(i*flow));
        }
        printf("%.6f %.6f
",final_filled,all_filled);
    }
    return 0;
}

View Code

二分代码：

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
ll c[maxn],sum;
int N;
double flow;

bool judgeAll(double t) {//判断所有的池塘是不是都满了
    double lef = 0;
    for(int i = 1; i<=N; i++) {
        lef += flow*t - c[i];
        if(lef >= sum) return true;//已经注入的水就灌满所有的池塘了
        if(lef < 0) return false;//前i个池塘已经灌入的水都灌不满前i个池塘，所有的池塘就更管不满了
    }
}

bool judgeFinal(double t) {//判断最后一个池塘是不是满了
    if(judgeAll(t))//如果所有的池塘都满了，最后一个肯定也满了
        return true;
    else {
        ll temp = 0;
        for(int i = N; i>=1; i--) {//逆序判断后i个池塘的水能不能全部灌满后i个池塘
            temp+=c[i];
            if(t*(N-i+1)*flow > temp)
                return true;
        }
        return false;
    }
}

int main() {
    while(scanf("%d",&N)!=EOF) {
        scanf("%lf",&flow);
        sum = 0;
        ll maxC = -1;
        for(int i = 1; i<=N; i++) {
            scanf("%d",&c[i]);
            sum += c[i];
            maxC = max(maxC, c[i]);
        }
        double final_filled,all_filled;
        double st = 0, en = 1.0*maxC/flow,mid;//最大的池塘的容量/流速 = 可能的最长的时间
        //cout<<en<<endl;
        for(int i = 1; i<=100; i++) {
            mid = (st+en) / 2;
            if(judgeAll(mid))
                en = mid;
            else
                st = mid;
            //cout<<mid<<endl;
        }
        all_filled = mid;
        st = 0, en = 1.0*maxC/flow,mid=0;
        for(int i = 1; i<=100; i++) {
            mid = (st+en) / 2;
            if(judgeFinal(mid))
                en = mid;
            else
                st = mid;
        }
        final_filled = mid;
        printf("%.6f %.6f
",final_filled,all_filled);
    }
    return 0;
}

View Code