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

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. *
NIEPRAWDA, PATRZ EDIT

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 :)

#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(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;
}

PS:
Przeprasza że wklejam zadanie i nie wygląda zbyt ładnie, ale nie mogę dać linku ponieważ żeby mieć dostęp do zadania trzeba się zalogować

EDIT:
Moje rozwiązanie jest błędne np. dla takich danych:
1
6 2
6 5 3 4 2 2

Zamiast odpowiedzieć 11 (6 + 5) (3 + 4 + 2 + 2) da wynik 13 :(

Czy problem można rozwiązać korzystając z dodatkowych bibliotek? Wygląda to na typowe zadanie z programowania liniowego, do którego są stworzone gotowe narzędzia.

Na szybko popraw

days.erase(mini) 

na

days.erase(days.lower_bound(mini)); 

Powinno działać, choć nie jest to idealne rozwiązanie; Jak zauważyłeś usuwasz wszystkie 9, a nie jedną.

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 :(

Rzeczywiście, Twój kontrprzykład obala chyba cały algorytm. Nic innego i prostego mi nie przychodzi do głowy.
Nadal uważam, że to zadanie trzeba rozwiązać metodami programowania liniowego.

Nie przeczytałem uważnie zadania (a przez to że wklejone jest średnio czytelne też trudno było to zauważyć w poście)

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).

trzeba zachować kolejność zadań, trzeba podzielnić je na k spójne ciągi, co zmienia kompletnie zadanie

Moja podpowiedź jak to zrobić: https://godbolt.org/z/c3W6zT

int planExam(int days, const std::vector<int>& tasksConsts)
{
    auto sum = std::accumulate(tasksConsts.begin(), tasksConsts.end(), 0);
    auto minimum = (sum + days - 1) / days;
    auto forcedMax = std::max(minimum, *std::max_element(tasksConsts.begin(), tasksConsts.end()));

    // todo

    return forcedMax;
}

naiwna implementacja (oparta o warunki konieczne, ale niewystarczające), przechodzi wszystkie testy z przykładu :)

@MarekR22: Też o tym pomyślałem

#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];
    }

    ll sum = accumulate(exe.begin(), exe.end(), 0);
    ll minimum = (sum + k - 1) / k;

    ll act = 0, ans = max(minimum, *max_element(exe.begin(), exe.end()));
    for (int i = 0; i < n; i++){
        if (act + exe[i] > minimum){
            ans = max(ans, act);
            act = exe[i];
        }
        else{
            act += exe[i];
        }
    }
    ans = max(ans, act);

    cout << ans << "\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;
}

Niestety nie przechodzi wszytskich testów (przykładowe są OK), chyba że mówiłeś o czymś innym to chętnie sprawdzę :)

Powymyślaj bardziej złośliwe przypadki danych wejściowych, np to: https://godbolt.org/z/eohaK5 (twój kod, tylko lekko przerobiony).

@Suchy702 Mam jeszcze jezdną podpowiedź: Co by było jakbyś miał obliczyć potrzebną ilość dni, jeśli miałbyś zadany limit czasu na jeden dzień?

Jest progres

#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 == (ll)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 max_limit = 0;
    for (int i = 0; i < n; i++){
        max_limit += exe[i];
    }
    ll min_limit = (max_limit + k - (ll)1) / k;
    while (min_limit < max_limit){
        ll mid = (min_limit + max_limit) / (ll)2;
        if (is_good_limit(mid, exe, k))
            max_limit = mid;
        else 
            min_limit = mid + (ll)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;
}

          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;
}

Taki kod daje błąd dopiero przy 5 pliku z testami (wcześniej zawsze dawał błąd przy 2), zmieniłem maximum jakie mi podawałeś na sume wszystkich elementów, bo to wcześniej napisałeś dawało złe wyniki już przy 2 pliku, jednak dalej jest gdzieś błąd

EDIT:
Problemem był acumulate(), myślałem że przyjmuje on wartości zmiennej do której ma być przyporządkowany, okazało się że on dodawał chyba w int ? Nie wiem ale dla dużych danych dawał złe wyniki, po zmienieniu na zywkła pętle dodająca do siebie wszystkie elementy jest zaakceptowane :)
Lub przekaznie do acumulate 0 zrzutowanego na long long

Suchy702 napisał(a):

Problemem był acumulate(), myślałem że przyjmuje on wartości zmiennej do której ma być przyporządkowany, okazało się że on dodawał chyba w int ? Nie wiem ale dla dużych danych dawał złe wyniki, po zmienieniu na zywkła pętle dodająca do siebie wszystkie elementy jest zaakceptowane :)
Lub przekaznie do acumulate 0 zrzutowanego na long long

W C++ to do czego się przyporządkowuje wartość zwracaną nie ma wpływu na na typ wartości zwracanej (i chyba żaden język nie ma takiej funkcjonalności).
jako że do std::accumulate podałeś literał 0, który ma typ int to taki typ był wartości zwracanej, prowadząc do integer overflow w późnych testcase sprawdzających granice możliwości twojego kodu.

Rozumiem, że już zaliczyłeś zadanie.

Tak sobie czytam i nadal nie jasne co trzeba zminimalizować, jedyne co znalazłem (tutaj jest formuła)