Cerința

Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

Avem n cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr A[i] reprezentând volumul cutiei i = 1,2...,n. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim k transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă x necesară pentru a efectua cele k transporturi. Numărul x este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!

Date de intrare

Pe prima linie a fișierului profu.in se vor găsi cele doua numere n și k cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi n numere naturale.

Date de ieșire

Fișierul de ieșire profu.out va conține pe prima linie numărul x, reprezentând capacitatea minima a mașini ce trebuie închiriată.

Restricții și precizări

1 ≤ n ≤ 500.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

profu.in

6 3
7 3 2 3 1 4

profu.out

Explicație

La primul transport este încărcată prima saltea (care are volumul 7). La cel de-al doilea transport sunt încărcate saltele 2 și 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt încărcate saltele 4, 5 și 6 (volumul total este 3 + 1 + 4 = 8 fiind cel mai mic rezultat posibil)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Profu:

#include <fstream>
#define Maxx 500001
using namespace std;
ifstream fin("profu.in");
ofstream fout("profu.out");
long long A[Maxx],k,sum,mx,trans,nw,n,i,st,dr,mij;
int main()
{
    fin>>n>>k;// pornim de pe considerentul ca valoarea cautata va fi intre maximul elementelor si suma lor
    for (i=1; i<=n; i++)
    {
        fin>>A[i];
        mx=max(A[i],mx);
        sum+=A[i];
    }
    st=mx;
    dr=sum;
    while (st<=dr)
    {
        trans=0;
        nw=0;
        mij=(st+dr)/2;
        for (i=1;i<=n;i++)
        {
            if (nw+A[i]>mij)
            {
                trans++;
                nw=A[i];
            }
            else
                nw+=A[i];
        }
        if (nw>0)
            trans++;
        if (trans>k)
            st=mij+1;
        else
            dr=mij-1;
    }
    fout<<st;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2252 Profu

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2252 Profu de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2252 Profu