Hey guys! Could anyone help me with debugging my code to this problem? I commented on every action I made so you can understand the code better.
#include <bits/stdc++.h>
using namespace std;
int vet[510], n, k;
//we need to search for the minimum value that each scriber can copy
bool buscaB (long long int mid) {
long long int tot = 1, cont = 0;
//tot is the number of scribers used until the moment
//cont is the number of pages a scriber is copying
for (int i=1; i<=n; i++) {
if (vet[i]>mid) return false;
//if the value is bigger than the bigger sum, then it is not the bigger sum
if (cont + vet[i]>mid) {
tot++;
cont = 0;
}
//if this happen, one more scriber is needed and we need to make cont 0
if (cont<=mid) {
cont += vet[i];
}
//we have to add the value to cont to see how much this scriber can write
}
if (tot<=k) return true;
//if we use less or k scribers, this is a possible option
else return false;
//if we use more, it isn't
}
int main() {
int t;
scanf ("%d", &t);
while (t--) {
scanf ("%d%d", &n, &k);
for (int i=1; i<=n; i++) scanf ("%d", &vet[i]);
long long int l = 0, r = 5000000010, mid;
//we start the binary search left and right as the lowest and more than maximum values
long long ans = 5000000010;
//ans is the maximum sum of pages one scriber can write
while (l<=r) {
mid = (l+r)/2;
if (buscaB(mid)==false) l = mid+1;
//we have to find a higher value so fewer scribers are needed
else {
ans = mid;
r = mid-1;
}
//this could be a possible answer, but we have to check if there is a lower one
}
long long int cont = 0;
//we are using cont to monitor where the / needs to be
deque<int> pos;
//pos keeps the positions we have to put a / after them
int j = 1;
//j is the number of scribers used until the moment
for (int i=n; i>=1; i--) {
//as the maximum sum has to be used by the last scriber, we start the for from n
if (i==k-j) {
//if the number of books left is equal to the number of / we have to put, we'll put a / after each one of them
cont=0;
pos.push_back(i);
j++;
}
if (cont+vet[i]>ans) {
//if the scriber has reached the maximum sum, we have to put a / and start the next scriber count
pos.push_back(i);
cont = 0;
j++;
}
if (cont<=ans) {
//if the count of the scriber is less than the maximum sum, we have to add more pages to it
cont += vet[i];
}
}
sort (pos.begin(), pos.end());
//we'll have the positions of the / in ascending order
for (int i=1; i<=n; i++) {
printf ("%d ", vet[i]);
//we have to print the value of the pages one scriber has to write
if (i==pos.front()) {
pos.pop_front();
printf ("/ ");
//if this is a position of /, we take one element of pos and print the /
}
}
printf ("\n");
}
return 0;
}