Puoi leggere e provare a risolvere il problema visitando la piattaforma Terry.
Iniziamo trovando la lunghezza minima.
Sappiamo che le righe esistenti devono rientrare nel limite di caratteri: questo significa che, per ogni riga, è almeno la lunghezza di quella riga, cioè la somma delle lunghezze delle parole più il numero di spazi (uguale al numero di parole della riga meno ).
Per calcolare è quindi sufficiente trovare la massima lunghezza di una riga esistente.
Inoltre, sappiamo che in ogni riga non devono entrare altre parole: in particolare, non può entrare la prima parola della riga successiva.
Quindi, per ogni riga (tranne quella finale), è al massimo la lunghezza di quella riga più la lunghezza della parola immediatamente successiva: se fosse maggiore, in quella riga potrebbero entrare uno spazio e la parola successiva, che quindi si troverebbe nella riga sbagliata.
è il minimo tra questi valori.
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
void solve(int t) {
int N;
cin >> N;
vector<int> W(N + 1);
for (int i = 0; i < N; i++) {
cin >> W[i];
}
int l = -1, min_l = 0, max_l = INT_MAX;
for (int i = 0; i < N; i++) {
if (W[i] == -1) {
min_l = max(min_l, l);
max_l = min(max_l, l + W[i + 1]);
l = -1;
} else {
l += W[i] + 1;
}
}
min_l = max(min_l, l);
cout << "Case #" << t << ": " << min_l << " " << max_l << "\n";
}
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}