[MeetCoder] Crossing Bridge

叁歲伎倆 2021-12-03 07:17 232阅读 0赞

## [Crossing Bridge][] ##

## Description ##

N people wish to cross a bridge at night. It’s so dark around there that they have to cross the bridge under the help of a little lamp. Only one little lamp is available (Oh, Men...) and they have to have the little lamp walking with them. The bridge is of a width such that a maximum of 2 people may cross at a time.

Each person walks at his/her fixed speed. If two people cross the bridge together, they must walk at the pace of the slower one. How fast can you get all N people over the bridge?

## Input ##

The input should be a list of N positive integers, where N is less than or equal to 1,000. And each integer of the list should be less than or equal to 100.

## Output ##

The output should be the minimum time that all the people can cross the bridge.

## Sample Input ##

1 2

## Sample Output ##

## HINT ##

Greedy

过桥问题！主要参考：[http://blog.csdn.net/morewindows/article/details/7481851][http_blog.csdn.net_morewindows_article_details_7481851]

1 class Solution {
     2 private:
     3     int _bridge(vector<int> &v, int n) {
     4         if (n == 0) return 0;
     5         if (n == 1) return v[0];
     6         if (n == 2) return v[1];
     7         if (n == 3) return v[0] + v[1] + v[2];
     8         int res = 0;
     9         int a = v[0], b = v[1], x = v[n-2], y = v[n-1];
    10         if (2 * b > a + x) res += 2 * a + x + y;
    11         else res += a + 2 * b + y;
    12         return res + _bridge(v, n - 2);
    13     }
    14 public:
    15     int bridge(vector<int> &v) {
    16         sort(v.begin(), v.end());
    17         return _bridge(v, v.size());
    18     }
    19 };
    20 /**************************************************************
    21     Problem: 45
    22     User: easonliu
    23     Language: C++
    24     Result: Accepted
    25     Time:1 ms
    26     Memory:2708 kb
    27 ****************************************************************/

转载于:https://www.cnblogs.com/easonliu/p/4646580.html

[Crossing Bridge]: http://www.meetcoder.com/problem.php?id=45
[http_blog.csdn.net_morewindows_article_details_7481851]: http://blog.csdn.net/morewindows/article/details/7481851