[PROGRAMMERS]救命ボート(レベル2)

4872 ワード
greedy level2 プログラマ テキストリンク

救命ボート(レベル2)


  • 質問リンク:コーディングテスト練習>欲張り>救命ボート

  • 問題を理解する
  • で与えられた収容重量より小さいために、人員を搭載可能な船の最大数を求める.
  • の場合、収容できる人員は2名です.

  • アルゴリズム実装
  • の人数が2人に制限されているので、2人乗船と1人乗船に分けられます.
  • 二人乗りの場合、二人の重量総和は限界より小さい.そのため、2人の人員は
    一致条件を考慮する必要があります.
  • 一番重い人と一番軽い人を結びつけるのが有効だと思います.
    そうだと思った.一番軽い人と一番軽い人が一緒に船に乗れないなら、
    一番重い人は自分で座るしかないからです.
  • そのためまず人の群れを並べ替えて、最も重い人+最も軽い人は限度より小さいです
    もしそうなら、二人を搭乗させて、船を1隻数えて、一番重い人+一番軽い人
    limitより大きい場合は、一人で搭乗し、ボートをカウントします.

  • アルゴリズム#アルゴリズム#
    • #include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    int n = people.size();
    int end = n - 1;
    int beg = 0;
    sort(people.begin(), people.end(), greater<int>());
    while (beg <= end) {
        if (people[beg] + people[end] <= limit) {
            ++beg;
            --end;
            answer += 1;
        }
        else {
            ++beg;
            answer += 1;
        }
    }
    return answer;
}
    XCode9でのFastlane/Snapshotの実行
    [Baekjoon][Python]2606号ウイルス