array-division

Array Division

CSES hard

يُعطى لك مصفوفة من \(n\) أعداد صحيحة موجبة. قسّم المصفوفة إلى \(k\) مصفوفات جزئية (أجزاء متصلة) بحيث يكون أكبر مجموع لمصفوفة جزئية أصغر ما يمكن.

القيود:

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le k \le n\)
\(1 \le x_i \le 10^9\)

الإدخال:

السطر الأول: عددان صحيحان \(n\) و \(k\).
السطر الثاني: \(n\) عددًا \(x_1, x_2, \dots, x_n\).

المخرجات:

عدد صحيح واحد — أكبر مجموع لمصفوفة جزئية في التقسيم الأمثل.

مثال:

الإدخال:

5 3
2 4 7 3 5

المخرجات:

(أحد التقسيمات المثلى هو \([2, 4]\) و \([7]\) و \([3, 5]\)، ومجاميعها \(6\) و \(7\) و \(8\).)

الحل

نستخدم البحث الثنائي على الجواب، كما في مسألة Factory Machines.

نثبّت حدًا \(L\) ونسأل: هل يمكن تقسيم المصفوفة إلى \(k\) مصفوفات جزئية على الأكثر بحيث لا يزيد أي مجموع عن \(L\)؟ إذا كان ذلك ممكنًا للحد \(L\)، فهو ممكن أيضًا لكل حد أكبر منه، لذلك يجد البحث الثنائي أصغر حد \(L\) ممكن. التقسيم إلى أقل من \(k\) مصفوفات جزئية يمكن دائمًا تقسيمه أكثر إلى \(k\) مصفوفات جزئية بالضبط، لأن كل عنصر وحده مصفوفة جزئية و \(k \le n\).

لفحص الحد \(L\) نستخدم طريقة جشعة: نمر من اليسار إلى اليمين ونضيف كل عنصر إلى المصفوفة الجزئية الحالية ما دام المجموع لا يزيد عن \(L\). عندما لا يتسع العنصر التالي، نبدأ به مصفوفة جزئية جديدة. جعل كل مصفوفة جزئية أطول ما يمكن لا يزيد أبدًا عدد المصفوفات الجزئية، لذلك يكون الحد ممكنًا تمامًا عندما تستخدم الطريقة الجشعة \(k\) مصفوفات جزئية على الأكثر.

مجال البحث:

الجواب لا يقل عن أكبر عنصر، لأن هذا العنصر يقع في مصفوفة جزئية ما. وهذا يضمن أيضًا أن كل عنصر يتسع وحده في مصفوفة جزئية.
الجواب لا يزيد عن مجموع كل العناصر (مصفوفة جزئية واحدة).

كل فحص يستغرق \(O(n)\)، لذا يعمل الحل كله في زمن \(O(n \log (\sum x_i))\).

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

int n, k;
vector<long long> x;

// can the array be divided into at most k subarrays with sums at most limit?
// limit is never smaller than the largest element
bool possible(long long limit) {
    int subarrays = 1;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (sum + x[i] > limit) {
            subarrays++;  // start a new subarray at x[i]
            sum = 0;
        }
        sum += x[i];
    }
    return subarrays <= k;
}

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

    x.resize(n);
    long long largest = 0, total = 0;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        largest = max(largest, x[i]);
        total += x[i];
    }

    long long left = largest, right = total;
    long long answer = total;

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

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

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

يصل مجموع كل العناصر إلى \(2 \cdot 10^{14}\)، لذلك نستخدم long long للمجاميع والحدود.