Loading...

プレビュー

全24ステップ中8ステップのみ表示

ログインして全て見る

銀行窓口配置

中級

Bank Counter Assignment

N人の顧客をM個の窓口で最短時間で処理するパラメトリック探索問題

📊 計算量

区分	計算量
最良	O(M log(max*N))
平均	O(M log(max*N))
最悪	O(M log(max*N))
空間	O(1)

🏷️ Tags

二分探索パラメトリック探索コーディングテスト

📋 問題

銀行窓口配置

忙しい月末、銀行にN人の顧客が待っています。 M個の窓口があり、各窓口で1人の顧客を処理するのにかかる時間が異なります。窓口が空くと、待っている顧客の中で最初の人がその窓口に行きます。すべての顧客を処理するのに必要な最短時間を求めてください。

1/24

Loading...

🏦忙しい月末の銀行!

6人の顧客が待機中。窓口1は7分、窓口2は10分ごとに1人処理。全員処理に最短何分必要？

銀行窓口配置

問題説明

忙しい月末、銀行にN人の顧客が待っています。 M個の窓口があり、各窓口で1人の顧客を処理するのにかかる時間が異なります。窓口が空くと、待っている顧客の中で最初の人がその窓口に行きます。すべての顧客を処理するのに必要な最短時間を求めてください。

入力

1行目: 顧客数 N (1 <= N <= 1,000,000,000) 2行目: 各窓口の処理時間の配列

出力

すべての顧客を処理する最短時間

制約条件

•1 <= N <= 1,000,000,000
•1 <= M (窓口数) <= 100,000
•1 <= 各窓口の処理時間 <= 1,000,000,000

例

例 1

入力

6
[7, 10]

出力

説明

28分間: 窓口1(7分)で4名(7, 14, 21, 28分)、窓口2(10分)で2名(10, 20分)を処理 = 合計6名

銀行窓口配置 | AlgoNote