iT邦幫忙

1

【zerojudge惡龍題】- d872: 過橋問題

今天分享一道「過橋問題」,
這是一道經典問題,
讀者可以先在Cross The Bridge - IQ Game這個網站上玩過會比較有感覺

https://ithelp.ithome.com.tw/upload/images/20200712/20117114NwbAy3w1B4.png

這遊戲是說每個人的過橋時間分別是1,2,4,6,8,12秒,
橋上每次最多只能容許2個人行走。

由於全部只有一支手電筒,
所以每次2個人拿著手電筒過橋後,
必須有一人再把手電筒拿回來,
問你要怎麼走才能讓他們在30秒內過橋?

策略解析

先以本遊戲做為分析,
每次我們思考如何將走最慢的兩個人送到橋的對岸?

交給最快的人傳手電筒就好?

由於每次都要有一個人回來,
最直覺的方法是讓走最快的那個人擔任來回傳手電筒的角色,
因為慢的人要再從對岸走回來感覺上很浪費時間

譬如說最慢的兩人是8秒和12秒,
如果由最快的人負責送手電筒的話,
那時間就是12+1+8+1=22秒。

  1. 1秒和12秒過橋(花12秒)
  2. 1秒從橋對岸回來(花1秒)
  3. 1秒和8秒過橋(花8秒)
  4. 1秒從橋對岸回來(花1秒)

然後我們就發現,把8秒和12秒送到橋對岸之後,
我們就快要沒有時間過橋了

改良: 最快的兩人負責傳遞手電筒

其實因為8秒和12秒都走的很慢,
最理想的狀況是讓8秒和12秒一起過橋,
這樣走的時間就是12秒而非(8+12)秒了,
大大節省時間

因此我們有個乍看之下不太直覺的策略:

  1. 先讓1秒和2秒兩個人過橋(花2秒)
  2. 1秒從橋對岸回來(花1秒)
  3. 8秒和12秒過橋(花12秒)
  4. 2秒從橋對岸回來(花2秒)

一樣把8秒和12秒都送到橋對岸,
但是這次只花了2+1+12+2=17秒

若你看懂這個策略後,
遊戲應該就會過關了,
祝你順利將6個人都送到橋對岸

一般情形- n人過橋

一般化的情形,就是本題的d872: 過橋問題了,
其實「最快的兩人負責傳遞手電筒」的策略不一定較好,
譬如說有四個人的過橋時間為1, 98, 99, 100秒,
因為98秒實在走太慢了,
讓98秒從橋對岸走回來很浪費時間,還不如讓1秒來回跑就好

因此,
我們要從兩種策略中取省時的來走,
假設最快、次快、次慢、最慢的四個人編號分別為A,B,Y,Z:

  1. AB一起過橋 -> A帶回手電筒 -> YZ一起過橋-> B帶回手電筒:花費時間 B+A+Z+B。
  2. AZ一起過橋 -> A帶回手電筒 -> AY一起過橋-> A帶回手電筒:花費時間 Z+A+Y+A。

找兩個方案時間最短的,
這樣一次送兩個人過橋,
直到只剩三人以下要過橋,
便能夠輕鬆算出過橋時間了

程式碼:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//v是每個人的過橋時間,需排序過,
//回傳這些人的總過橋時間
int crossBridge(vector <int> &v){
    int ans = 0;
    while (v.size() >= 4){
        int x = v[0] * 2 + v[v.size()-2] + v[v.size()-1];
        int y = v[0] + v[1] * 2 + v[v.size()-1];
        ans += min(x, y);
        v.resize(v.size()-2);
    }
    if (v.size() == 3){
        for (int i:v){
            ans += i;
        }
    }
    else if (v.size() == 2){
        ans += v[1];
    }
    else{
        ans += v[0];
    }
    return ans;
}
 
int main(){
    int n;
    while (scanf("%d", &n)!= EOF){
        if (n == 0){
            printf("0\n");
            continue;
        }
        vector <int> v(n);
        for (int i = 0; i < n; i++){
            scanf("%d", &v[i]);
        }
        sort(v.begin(), v.end());
        printf("%d\n", crossBridge(v));
    }
}

尚未有邦友留言

立即登入留言