[コードテストC+]入国審査

今日の質問

入国審査

マイ解答(参考後解答)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    unsigned long long end = n * times[times.size()-1];
    unsigned long long start = 1;
    unsigned long long answer = 0;
    while(start <= end){   
        unsigned long long mid = (start + end)/2;
        unsigned long long people = 0;
        
        for(int i=0;i<times.size();i++){
            people += mid / times[i];
        }
        if(people >= n){
            if(answer == 0)
                answer = mid;
            else
                answer = min(answer, mid);
            end = mid-1;
        }else{
            start = mid+1; 
        }
    }
    return answer;
}

模範解答

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());

    long long left = (long long)times[0];
    long long right = (long long)times[times.size() - 1] * n;
    long long answer = right;
    while(left <= right){
        long long mid = (right + left) / 2;
        long long pass = 0;

        for(int i = 0; i < times.size(); ++i)
            pass += mid / (long long)times[i];

        if(pass >= n){
            right = mid - 1;
            if(mid <= answer)
                answer = mid;
        }
        else 
            left = mid + 1;
    }
    return answer;
}

学ぶべきところ

に署名されていないlong longは約0億から18億円です.