マツシタのお勉強

ドワンゴからの挑戦状 C - スキーリフトの相乗り

問題

C: スキーリフトの相乗り - 第3回 ドワンゴからの挑戦状 予選 | AtCoder

解法

リフトの定員は4人。乗客を効率よく載せて、使用するシフト数を最小にする問題。条件を満たすような乗客の載せ方は、なるべく多くのリフトに定員数の4人を載せること。4人乗ったリフト数を最大化するように乗客を載せることで使用するリフト数を最小化することができる。


何人グループが何組存在するかを配列で保持。

nums[1] = 1人グループの数
nums[2] = 2人グループの数
nums[3] = 3人グループの数
nums[4] = 4人グループの数


nums[4]はその値がそのままリフト数になる。
nums[3]もその値がそのままリフト数になるが、1席空いているのでnums[1]からnums[3]の値だけ乗せる。
nums[2]は2グループで1つのリフトに乗るようにする。
nums[2]が奇数の場合は2人グループが1つ余るので、nums[1]から2人だけ相乗りさせる。
残りのnums[1]を4人ずつ相乗りさせれば、答えを導ける。

ソースコード