ZeroJudge O711: 裝飲料

有一個杯子，可將其體積視為由兩個長方體組成（如下圖），下方的長方體底面積為 w1 × w1 cm2，高為 h1 cm，上方的長方體底面積為 w2 × w2 cm2，高為 h2 cm。

一開始杯子為空。要裝 n 次飲料，每一次裝 v cm3 容量的飲料，當水杯滿時水位不再上升。問這 n 次倒飲料中水位上升變化量最高是幾 cm。 

範例測資

範例輸入範例輸出
第一行有一個正整數 N (1 ≤ N ≤ 10)，代表要裝 N 次飲料。
接下來一行有 4 個正整數 w1、w2、h1、h2 (1 ≤ w1、w2、h1、h2 ≤ 50)，代表杯子的寬度與高度。
最後一行有 N 個正整數代表每次裝飲料的容量。保證每次水位上升都是整數。		輸出這 N 次倒水中，上升變化量最大的高度為何。
1
4 6 8 5
200		10
2
5 10 12 8
400 600		13
5
16 44 28 17
2560 1280 1536 1024 10448		10

解題思路

使用前綴和的方式去判斷每一次裝的水從最下面開始裝會上升多少高度，然後減去上一次水位上升的高度就是這次水位上升的高度了。

範例程式碼－ZeroJudge O711: 裝飲料

#include <iostream>
using namespace std;

int N, w1, w2, h1, h2;
int first, second;

int calcLevel(const int w) {
    int level;
    if (w <= first) {
        level = w / (w1*w1);
    }
    else if (w <= first + second) {
        level = h1 + ((w-first) / (w2*w2));
    }
    else {
        level = h1 + h2;
    }
    return level;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> w1 >> w2 >> h1 >> h2;
    first = w1 * w1 * h1;
    second = w2 * w2 * h2;
    int water[20] = {}, prefix[20] = {}, calc[20] = {}, ans = -999;
    prefix[0] = 0;
    calc[0] = 0;
    for (int i = 0; i<N; i++) {
        cin >> water[i];
        prefix[i+1] = prefix[i] + water[i];
    }
    for (int i = 0; i<N; i++) {
        const int level = calcLevel(prefix[i+1]);
        calc[i+1] = level;
        ans = max(ans, level-calc[i]);
    }
    cout << ans << "\n";
}

//ZeroJudge O711
//Dr. SeanXD
標籤

相關文章

發佈留言