Uva13054 - Hippo Circus

題目大意

一堆河馬要過門，但是一個一個過太慢，所以我們讓他們可以最多兩個河馬疊在一起過，但要注意兩個河馬加起來的高度不能超過或等於門的高度，問最少花多少時間可以讓所有河馬都穿過門。

重點觀念

• 有點水

分析

• 大配小

程式題目碼

#include <string.h>

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        int N, H, Ta, Td;
        cin >> N >> H >> Ta >> Td;

        int height[N];
        bool used[N];
        memset(used, false, sizeof(used));

        for (int i = 0; i < N; i++) {
            cin >> height[i];
        }

        sort(height, height + N);

        int other_index = N - 1;
        int ans = 0;
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                continue;
            }

            while ((used[other_index] || (height[i] + height[other_index]) >= H) && other_index > i) {
                other_index--;
            }

            if (other_index > i && (Ta + Ta) > Td) {
                used[other_index] = true;
                ans += Td;
            } else {
                ans += Ta;
            }

            used[i] = true;
        }

        cout << "Case " << t << ": " << ans << endl;
    }
    return 0;
}