Pond Cascade Gym - 101670B 貪心+數學
摘要：
題目：題目連結
思路：題目讓求最下面池子滿的時間和所有池子滿的時間，首先我們考慮所有池子滿的時間，我們從上到下考慮，因為某些池子滿了之後溢位只能往下溢水，考慮當前池子如果注滿時間最長，那麼從第一個池子到當前池子容量之和與流速之和之比是一樣的，隨著資料讀入處理一遍即可得出最大...
題目：ofollow,noindex">題目連結
思路：題目讓求最下面池子滿的時間和所有池子滿的時間，首先我們考慮所有池子滿的時間，我們從上到下考慮，因為某些池子滿了之後溢位只能往下溢水，考慮當前池子如果注滿時間最長，那麼從第一個池子到當前池子容量之和與流速之和之比是一樣的，隨著資料讀入處理一遍即可得出最大的注滿時間，即注滿全部池子的時間，接下來我們考慮最下方池子的注滿時間，這個時間不會大於單獨給這個池子注滿的時間，同樣的，不會大於給最下方池子和他上面那一個池子一塊拿出來後最下方池子的注滿時間，反著掃描一遍，就可以得出結果。
AC程式碼：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cmath>
5 #include <algorithm>
6 #include <cstring>
7 #include <vector>
8 #include <string>
9 #include <queue>
10 #include <map>
11 #include <set>
12
13 #define FRER() freopen("in.txt", "r", stdin);
14 #define INF 0x3f3f3f3f
15
16 using namespace std;
17
18 int main()
19 {
20//FRER()
21int n, num[100005];
22double m, minans, sumans, sum, sumv;
23while(~scanf("%d %lf", &n, &m)) {
24scanf("%d", &num[0]);
25sum = 1.0 * num[0];
26sumv = m;
27sumans = sum / sumv;
28for(int i = 1; i < n; ++i) {
29scanf("%d", &num[i]);
30sum += 1.0 * num[i];
31sumv += m;
32sumans = max(sumans, sum / sumv);
33}
34sum = 1.0 * num[n - 1];
35sumv = m;
36minans = sum / sumv;
37for(int i = n - 2; ~i; --i) {
38sum += 1.0 * num[i];
39sumv += m;
40minans = min(minans, sum / sumv);
41}
42printf("%.8f %.8f\n", minans, sumans);
43}
44return 0;
45 }