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