Jak rozłożyć n liczb na k dni aby max(ki) było najmniejsze ?

Question

Mam takie zadanie:

You will have a math exam in k days. So you decided to prepare for it by solving n problems. It takes you ai minutes to solve the i-th problem. You want to solve the problems in the order they are numbered (i. e., the problem number i+1 can only be solved after you solve the problem number i).
You want to distribute the problems between days: during the first day, you will solve several (maybe zero) first problems; during the second day, you will solve several (maybe zero) next problems, and so on. You can't split a problem between different days, and all problems should be solved. To make sure you don't get overloaded, you want to distribute the problems between days as evenly as possible. Formally, let ti
be the time you spend solving the problems during the i-th day; you have to minimize (tutaj jest formuła).

Input
The first line contains a single integer t (1≤t≤10^4) — the number of test cases. The first line of each test case contains two integers n and k (1≤k≤n≤2⋅10^5) — the number of problems you have to solve and the number of days before the exam.

The second line of each test case contains n integers a1,a2,…an (1≤ai≤10^9) — the time required to solve the i-th problem.
It's guaranteed that the total sum of n over all test cases doesn't exceed 2⋅10^5

Output
For each test case print one integer — the minimum value of maxi=1kti

Example
Input

4
5 3
3 5 8 2 7
4 4
7 1 3 6
3 1
4 8 7
5 2
4 4 3 6 4

Output

9
7
19
11

Widomo że pierwsze największe k liczb ze zbioru n muszą być w osobnych dniach. Więć podzeliłem je tak wkładając je do multiset, następnie do najmniejszej z wszystkch liczb w tym multisecie dodaje najwięszką pozostała liczbę ze zbioru n aż do końca tego zbioru.

Moje rozwiązanie nie przechodzi testów, niestety też nie mam do nich dostępu, nie wiem czy moje rozwiązanie jest błędne, czy popełniam jakiś błąd w kodzie. Proszę o pomoc w znalezeniu błędu :)

EDIT: Poprawiłem kod, niestety dalej nie przechodzę testów

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

const int INF = 1e9 + 7;

void solve(){       
    ll n, k;
    cin >> n >> k;
    vector<ll> exe(n);
    for (int i = 0; i < n; i++){
        cin >> exe[i];
    }

    sort(exe.begin(), exe.end());
    multiset<ll> days;

    for (int i = n-1; i >= 0 && i > n - k - 1; i--){
        days.insert(exe[i]);
    }

    for (int i = n - k - 1; i >= 0; i--){
        ll mini = *(days.begin());
        days.erase(days.lower_bound(mini)); 
        days.insert(mini + exe[i]);
    }

    cout << *(--days.end()) << "\n";
}   

void testcases(){
    int t;
    cin >> t;
    while(t){
        solve();
        t--;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    testcases();
    //solve();
    return 0;
}

Dla takich danych mój pomysł jest błędny:
1
5 2
6 5 3 4 4

Poprawna odpowiedź to 11 (6 + 5) i (3 + 4 + 4)
Według moje pomysłu wyszłoby 12:
6 5 <- do 5 dodajemy 4
9 6 <- do 6 dodajemy 4
10 9 <- do 9 dodajemy 3
10 12 :(

Answer 1

Problemem jest to, że liczby w każdej grupie muszą być spójnym podciagiem ciągu wejściowego. Wydaję mi się, że gdyby nie było takiego ograniczenia to nie dałoby się tego zadania rozwiazać w jakiejś sensownej złożoności, więc trzeba własnie skorzystać z tego, że to musi być spójne

Comments

optymalna = ceil(Suma_wszystkich_zadań / k), i lecimy gąsienicą szukając "optymalnej" ?

---

Niestety nie

---

Zrobiłem coś takiego, ale teraz mam błąd w 5 teście

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

const int INF = 1e9 + 7;

bool is_good_limit(ll limit, vector<ll>& exe, ll k){
    int i = 0;
    for (; i < (int)exe.size() && k > 0; k--){
        ll act_sum = 0;
        for(; act_sum + exe[i] <= limit && i < (int)exe.size(); i++){
            act_sum += exe[i];
        }
    }

    return k > 0 || (k == 0 && i == (int)exe.size());
}

void solve(){       
    ll n, k;
    cin >> n >> k;
    vector<ll> exe(n);
    for (int i = 0; i < n; i++){
        cin >> exe[i];
    }

    ll min_limit = (accumulate(exe.begin(), exe.end(), 0) + k - 1) / k;
    ll max_limit = accumulate(exe.begin(), exe.end(), 0);
    while (min_limit < max_limit){
        ll mid = (min_limit + max_limit) / 2;
        if (is_good_limit(mid, exe, k))
            max_limit = mid;
        else 
            min_limit = mid + 1;
    }

    cout << min_limit << "\n";
}   

void testcases(){
    int t;
    cin >> t;
    while(t){
        solve();
        t--;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    testcases();
    //solve();
    return 0;
}

Może źle sprawdzam czy jest możliwe podzielenie na dni z takim limitem?

 

EDIT: Problemem był acumulate, bo przekzywałem do niego 0 a nie (ll)0 i wywalało poza int, po zminiach AC :D