UVa13054 - Hippo Circus(設計解題、貪心)

題目大意

有一組馬戲團要表演，其中要表演河馬走鋼索，他們可以選擇一隻河馬走鋼索，會使用 \(T_a\) 秒、兩隻河馬疊在一起一起走鋼索，會使用 \(T_b\) 秒，但由於馬戲團的每一個部門都必須表演，且不能讓時間太長，因此請幫助河馬使用最少的秒數完成表演。

其中每隻河馬都有不同的高度，如果選擇兩隻河馬疊在一起一起走鋼索那他們相加起來的高度不可以大於出場門的高度，否則會撞到門。

重點觀念

• 直接了當地解決問題
• 使用貪心解決問題
  • \(T_a * 2 < T_b \)
  • 如何讓兩隻河馬疊起來卻不超過門的高度呢？

分析

• 如果\(T_a * 2 < T_b \)，那我就讓每隻河馬都自己走自己的就好。
• 如何讓兩隻河馬疊起來卻不超過門的高度呢？
  • 先進行排序
  • 讓最大河馬高度與最小河馬高度相加，如果有大於門的高度，就讓最大的河馬自己走
  • 如果沒有大於門的高度，就讓最大的河馬與最小河馬高度一起走
  • 我們用左、右邊界來實現這部分。
• 如此一來我們就可以順利讓所有的河馬都可以達到完美匹配，讓疊在一起的河馬高度不會大於門。

參考連結

Uva13054 - Hippo Circus by txya900619

心得

一開始我想的太複雜，後來發現我應該這樣思考就好。 也是看完力瑋的文章後才有更好的啟發，可以把它寫得更乾淨。
謝謝力瑋啦。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
int c, n, h, ta, tb, kase=0;
int num[MAXN];

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> c;
    while(c--){
        cin >> n >> h >> ta >> tb;
        for(int i = 0; i < n; i++) cin >> num[i];
        sort(num, num+n); //蒐集每個河馬高度，然後排序

        int L=0, R=n-1, ans=0;

        while(R > L){ //左右指針去查詢
            //如果 ta*2 比 tb 大才值得兩個河馬疊起來
            //河馬 R + 河馬 L 高度要比 h 小
            if(ta * 2 > tb && num[R] + num[L] < h){ 
                R--; //左右邊界各縮減一，表示都被使用過
                L++;
                ans += tb;
            }
            else{
                R--; //讓最大的自己走。
                ans += ta;
            }
        }
        //防止中間那隻河馬沒有人跟他配，所以要確認。
        //也不可以寫 while(R >= L) 這樣中間那隻河馬跟他自己疊起來 < h 時不合理。
        if(R == L) ans += ta; 
        cout << "Case " << ++kase << ": " << ans << '\n';
    }

    return 0;
}