Cerința

Pe axa reală există N orașe, numerotate cu numerele 1, 2, 3, …, N. Deși într-o lume unidimensională lucrurile par a fi mult mai simple, totuși majoritatea locuitorilor sunt nemulțumiți de distanțele mari parcurse între orașe în scopul rezolvării diferitelor probleme. Astfel, pentru o mai bună organizare, s-a supus la vot și s-a decis promovarea a cel mult K orașe la rangul de centru adminstrativ. Centrele trebuie amplasate într-un mod isteț, în așa fel încât distanța maximă calculată dintre distanțele de la fiecare oraș la cel mai apropiat centru administrativ să fie cât mai mică. Întrucât costurile de administrare ale unui astfel de centru sunt ridicate, se dorește să se amplaseze un număr cât mai mic de centre administrative astfel încât distanța maximă să nu fie modificată.

Date de intrare

În fișierul orase1.in, pe prima linie se află separate prin spații numerele N și K. Pe linia următoare se află N-1 numere naturale nenule, separate prin spații, al i-lea număr reprezentând distanța dintre orașele i și i+1.

Date de ieșire

Fișierul orase1.out va trebui să conțină pe o singură linie, separate prin spațiu, două numere naturale, reprezentând distanța maximă corespunzătoare unei amplasări optime a centrelor, respectiv numărul orașelor ce trebuie promovate.

Restricții și precizări

2 ≤ N ≤ 1 000 000
1 ≤ K ≤ min(N, 1 000)
suma celor N-1 distanțe nu depășește 2 000 000 000

Exemplu

orase1.in

7 3
3 1 4 14 4 3

orase1.out

4 2

Explicație

O posibilitate de amplasare optimă a centrelor poate fi în orașele 3 și 6.

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

#include <fstream>
#define DIM 1000002
using namespace std;

unsigned int v[DIM];

unsigned int n, i, k, p, u, mid, dist, centre;

int sePoate(int d) {
    int s = 0;
    int i=2;
    while (s + v[i]  <= d && i<=n) {
        s += v[i];
        i++;
    }

    if (i > n) {
        return 1;
        //se poate cu un singur centru
    }

    centre = 1;
//    int lastcentru = i-1;

    for (;;) {
        s = 0;
        while (s + v[i]<= d && i<=n) {
            s += v[i];
            i++;
        }

        if (i<=n) {
            centre++;
            if (centre > k)
                return 0;
            s = 0;
            i++;
            if (i>n)
                return 1;

            while (s + v[i] <= d && i<=n) {
                s += v[i];
                i++;
            }

            if (i > n) {
                return 1;
                //se poate cu un singur centru
            }
        } else {
            return 1;
        }
    }
}

int main() {
    ifstream fin("orase1.in");
    ofstream fout("orase1.out");
    fin>>n>>k;
    for (i=2;i<=n;i++) {
        fin>>v[i];
        dist += v[i];
    }

    sePoate(4);

    p = 1;
    u = dist;

    while (p<=u) {
        mid = p + (u-p)/2;
        if (sePoate(mid))
            u = mid - 1;
        else
            p = mid + 1;
    }

    fout<<p;
    sePoate(p);
    fout<<" "<<centre<<"
";
    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 #681 orase1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #681 orase1 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 #681 orase1