鉄則本 A12 - Printer (3Q, ★3)

「答えで二分探索」のめちゃくちゃいい練習問題！

• 問題へのリンク

問題概要

台のプリンターがあり、 番目のプリンターは 秒後にプリントする。

合わせて 番目のプリントが行われるのは何秒後か？

制約

• 
• 
• 答えが 以下]

解法

鉄則本の問題なので、鉄則本参照。

1 つ言えるのは、 番目に小さい整数値を求めよと言われたら、次のような判定問題を考えて二分探索するといい！

---

以下の整数のうち、条件を満たすものが 個以上あるかどうかを判定せよ

---

この判定問題の答えが Yes であるような、最小の が求める値である！！

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    long long low = 0, high = 1LL<<40;
    while (high - low > 1) {
        long long x = (high + low) / 2;
        
        long long num = 0;
        for (int i = 0; i < N; ++i) num += x / A[i];
        
        if (num >= K) high = x;
        else low = x;
    }
    cout << high << endl;
}