Pagini recente » Cod sursa (job #626434) | Cod sursa (job #1976993) | Cod sursa (job #2676173) | Cod sursa (job #446461) | Cod sursa (job #3296086)
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
vector <int> sirDeSaltele;
int n, k;
bool PoateTransporta(int capacitate) {
int transporturi = 1;
int volumCurent = 0;
for (int i = 0; i < sirDeSaltele.size(); i++) {
if (volumCurent + sirDeSaltele[i] <= capacitate) {
volumCurent += sirDeSaltele[i];
}
else {
transporturi++;
volumCurent = sirDeSaltele[i];
if (transporturi > k) {
return false;
}
}
}
return true;
}
int main() {
int suma = 0, maxim = 0;
cin >> n >> k;
sirDeSaltele.resize(n);
for (int i = 0; i < sirDeSaltele.size(); i++) {
cin >> sirDeSaltele[i];
suma += sirDeSaltele[i];
maxim = max(maxim, sirDeSaltele[i]);
}
int stanga = maxim, dreapta = suma,rezultat = suma;
while (stanga <= dreapta) {
int mijloc = stanga + (dreapta - stanga) / 2;
if (PoateTransporta(mijloc)) {
rezultat = mijloc;
dreapta = mijloc - 1;
}
else {
stanga = mijloc + 1;
}
}
cout << rezultat;
return 0;
}