Bạn được cho một mảng chứa n số nguyên dương. Nhiệm vụ của bạn là chia mảng thành k đoạn con sao cho tổng lớn nhất trong các đoạn con nhỏ nhất có thể. Input Dòng đầu vào đầu tiên chứa hai số nguyên n và k: kích thước của mảng và số lượng đoạn con trong cách chia. Dòng tiếp theo chứa số nguyên x1,x2,...xn: nội dung của mảng. Output In một số nguyên: tổng lớn nhất của một đoạn con trong cách chia tối ưu. Constraints 1$\leq$ n $\leq$ $2.10^{5}$ 1$\leq$ k $\leq$ n 1$\leq$ xi $\leq$ $10^{9}$ Example Input 5 3 2 4 7 3 5 output 8 Ngôn ngữ C++ ạ

Thuật toán

Ta có thể sử dụng thuật toán tìm kiếm nhị phân cho bài này.

Gọi $s(i) = 1$ nếu có thể chia mảng thành $k$ phần với tổng của phần có tổng lớn nhất không vượt quá $i$, $s(i) = 0$ nếu ngược lại. Dễ thấy:

- Nếu $s(i) = 1$ thì $s(i+1) = 1$

- Nếu $s(i) = 0$ thì $s(i-1) = 0$

Do đó, công việc của chúng ta là tìm kiếm nhị phân giá trị $y$ nhỏ nhất sao cho $s(y) = 1$.

Vậy làm thế nào để cài đặt hàm $s(i)$ như trên?

Ta sẽ dùng thuật toán tham lam. Ta sẽ cố gắng nhét nhiều phần tử nhất có thể vào dãy con đầu tiên sao cho tổng của nó không vượt quá $i$, sau đó lại cố gắng nhét tiếp các phần tử chưa được nhét vào dãy con thứ hai...

$s(i) = 1$ khi và chỉ khi ta nhét được tất cả các phần tử của $x$ vào không quá $k$ mảng con.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

int n, k, a[maxn];
long long l,r,mid,sum;

bool check(long long x){
    // Kiem tra co the tao tong be hon hoac bang x
    long long cur=0, parts=0;
    for(int i=1;i<=n;i++){
        cur += a[i];
        if(cur > x){
            cur = a[i];
            parts++;
        }
    }
    if(cur > 0) parts++;
    return parts <= k;
}

int main(){
    cin >> n >> k;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        sum += a[i];
    }
    l=*max_element(a+1,a+n+1);r=sum;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout << l;
}

#include <bits/stdc++.h>
#define ll long long
#define el "\n"
#define fu(i, a, b) for(ll i = a; i <= b; i++)
#define fd(i, a, b) for(ll i = a; i >= b; i--)
#define fi first
#define se second

using namespace std;

ll n, k, a[200003], l, r, ans;

bool check(ll h)
{
    ll sum = 0, i = 1, cnt = 1;
    while (i <= n)
    {
        if (sum + a[i] <= h)
        {
            sum += a[i];
            i++;
        } else
        {
            cnt++;
            sum = 0;
        }
        if (cnt > k) return 0;
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    fu(i, 1, n)
    {
        cin >> a[i];
        l = max(l, a[i]);
        r += a[i];
    }
    while (l <= r)
    {
        ll mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}