factory-machines

Factory Machines

CSES medium

في مصنع \(n\) آلة تصنع منتجات. تحتاج الآلة رقم \(i\) إلى \(k_i\) ثانية لصنع منتج واحد. تعمل الآلات في الوقت نفسه، ويمكن لكل منها أن تصنع أي عدد من المنتجات.

أوجد أقل زمن يلزم لصنع \(t\) منتجًا.

القيود:

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le t \le 10^9\)
\(1 \le k_i \le 10^9\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(t\) — عدد الآلات وعدد المنتجات.
السطر الثاني: \(n\) عددًا \(k_1, k_2, \dots, k_n\).

المخرجات:

عدد صحيح واحد — أقل زمن.

مثال:

الإدخال:

3 7
3 2 5

المخرجات:

(خلال \(8\) ثوانٍ تصنع الآلات \(2\) و \(4\) و \(1\) منتجًا.)

الحل

خلال \(T\) ثانية تصنع الآلة رقم \(i\) عدد \(\lfloor T / k_i \rfloor\) منتجًا، لذلك تصنع كل الآلات معًا

\[ \sum_{i=1}^{n} \left\lfloor \frac{T}{k_i} \right\rfloor \]

منتجًا. نقول إن الزمن \(T\) كافٍ إذا كان هذا المجموع لا يقل عن \(t\).

إذا كان \(T\) كافيًا، فكل زمن أكبر منه كافٍ أيضًا. لذلك تأتي الأزمنة غير الكافية أولًا ثم تليها الأزمنة الكافية:

T:       1  2  3  4  5  6  7  8  9  ...
enough:  no no no no no no no yes yes ...

الجواب هو أول زمن كافٍ. هذا البحث هو نفسه الذي في الدرس، حيث بحثنا عن أول عنصر أكبر من أو يساوي \(X\). هنا لا نبحث في مصفوفة، بل نبحث في مجال الأجوبة الممكنة، وبدلًا من الشرط arr[mid] >= x نستدعي الدالة enough(mid). تُسمّى هذه التقنية البحث الثنائي على الجواب.

مجال البحث:

الجواب لا يقل عن \(1\).
أسرع آلة وحدها تصنع \(t\) منتجًا خلال \(\min(k_i) \cdot t \le 10^{18}\) ثانية، لذلك هذا الزمن كافٍ دائمًا.

كل استدعاء للدالة enough يستغرق \(O(n)\)، ويُجري البحث الثنائي نحو \(\log_2 10^{18} \approx 60\) استدعاءً، لذا يعمل الحل كله في زمن \(O(n \log (\min(k_i) \cdot t))\).

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

int n;
long long t;
vector<long long> k;

// can the machines make t products in `time` seconds?
bool enough(long long time) {
    long long products = 0;
    for (int i = 0; i < n; i++) {
        products += time / k[i];
        if (products >= t) {
            return true;  // stop early, so that products does not overflow
        }
    }
    return false;
}

int main() {
    cin >> n >> t;

    k.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> k[i];
    }

    // the fastest machine alone makes t products in this time
    long long left = 1;
    long long right = *min_element(k.begin(), k.end()) * t;
    long long answer = right;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (enough(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << "\n";
}

نقاط يجب الانتباه لها

تصل الأزمنة إلى \(10^{18}\)، لذلك نستخدم long long.
قد يكون مجموع المنتجات أكبر بكثير من \(10^{18}\) فيتجاوز سعة long long. لذلك تتوقف الدالة enough بمجرد أن يصل المجموع إلى \(t\).
left + (right - left) / 2 يساوي (left + right) / 2، لكن left + right قد يتجاوز السعة عندما تقترب القيمتان من \(10^{18}\).