プログラマー-入国審査(C++)
問題の説明
n人が並んで入国審査を待っています.入国審査台ごとに審査官が審査するのにかかる時間が異なります.
最初はすべての審査団が空いていました1つの審査台は同時に1人しか審査できない.一番前に立っている人は空いている審査台で審査を受けることができます.しかし、もっと早く終わった審査団があれば、そこで審査を受けるまで待つこともできます.
全員が審査を受けるのに要する時間を最小限に抑えたい.
各レビュー担当者に必要な時間の配列時間をパラメータとしてレビューするときに、すべての人がレビューを受け入れるのに要する時間の最大値を返す解決関数を書いてください.
せいげんじょうけん
入国審査待ち人数は1名以上10000000名以下.
各審査官が1人を審査するのに要する時間は1分以上10000000分以下である.
審査官は1名以上10万名以下です.
I/O例
n times return
6 [7, 10] 28
に答える
二分探索を用いて解決できる.
最短時間1、
監査に最も時間がかかる最大*人数
保持
1時間当たりの中間値を計算して何人を審査することができますか.
レビュー人数がnより大きい場合は最大時間を減らし、レビュー人数がnより小さい場合は最小時間を増やします.
n人が並んで入国審査を待っています.入国審査台ごとに審査官が審査するのにかかる時間が異なります.
最初はすべての審査団が空いていました1つの審査台は同時に1人しか審査できない.一番前に立っている人は空いている審査台で審査を受けることができます.しかし、もっと早く終わった審査団があれば、そこで審査を受けるまで待つこともできます.
全員が審査を受けるのに要する時間を最小限に抑えたい.
各レビュー担当者に必要な時間の配列時間をパラメータとしてレビューするときに、すべての人がレビューを受け入れるのに要する時間の最大値を返す解決関数を書いてください.
せいげんじょうけん
入国審査待ち人数は1名以上10000000名以下.
各審査官が1人を審査するのに要する時間は1分以上10000000分以下である.
審査官は1名以上10万名以下です.
I/O例
n times return
6 [7, 10] 28
に答える
二分探索を用いて解決できる.
最短時間1、
監査に最も時間がかかる最大*人数
保持
1時間当たりの中間値を計算して何人を審査することができますか.
レビュー人数がnより大きい場合は最大時間を減らし、レビュー人数がnより小さい場合は最小時間を増やします.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
long long tmpTime = *max_element(times.begin(), times.end());
long long minTime = 1;
long long maxTime = (long long)n*tmpTime;
long long mid = 0;
while(minTime <= maxTime) {
mid = (minTime + maxTime)/2;
long long sum = 0;
for(auto time:times){
sum += mid / time;
}
if (sum >= n) {
answer = mid;
maxTime = mid-1;
} else {
minTime = mid+1;
}
}
return answer;
}
Reference
この問題について(プログラマー-入国審査(C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@countryyoon/프로그래머스-입국심사-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol