Într-o tabără de vară se programează susținerea unor cursuri în K săli de clasă. Sunt N profesori care și-au exprimat dorința de a participa, fiecare dintre ei specificând intervalul de timp [ai, bi] în care își poate susține cursul. Programarea pe săli a profesorilor trebuie să țină cont de faptul că într-o clasă, la un moment dat, nu poate preda decât un singur profesor.
Cerința
Cunoscându-se faptul că organizatorii doresc susținerea a cât mai multor cursuri, să se determine:
1) Numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
2) În dorința de a programa toate cursurile, în cele K săli, organizatorii decid să modifice durata cursurilor, păstrând însă neschimbată ora de început a lor. Astfel, ei hotărăsc ca toate cursurile să dureze un interval egal de timp, care însă nu va depăși durata celui mai lung curs propus inițial de unul dintre cei N profesori. Determinați care poate fi durata maximă pe care o pot avea cursurile în aceste condiții.
Date de intrare
Fișierul de intrare cursuri.in conține pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe linia a doua se găsește o pereche de numere naturale N K, separate printr-un spațiu, reprezentând numărul profesorilor și numărul de săli de clasă. Pe următoarele N linii se găsesc perechi de numere naturale ai, bi, care reprezintă intervalele de timp în care cei N profesori își susțin cursurile. Numerele în cadrul unei linii sunt separate printr-un spațiu.
Date de ieșire
Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire cursuri.out va conține pe prima linie un număr natural reprezentând numărul maxim de cursuri care pot fi programate în cele K săli de clasă, ținând cont de restricția indicată.
Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire cursuri.out va conține pe prima linie un număr natural reprezentând durata maximă pe care o pot avea cele N cursuri, astfel încât toate să poată fi susținute în cele K săli disponibile.
Restricții și precizări
1 ≤ n ≤ 10001 ≤ K ≤ 1 0001 ≤ ai< bi≤ 100 000, unde1 ≤ i ≤ N- În cazul cerinței 2) se garantează că pentru toate testele există soluție
- Pentru rezolvarea corectă a primei cerinţe se acordă 45 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. Se acordă 10 puncte pentru exemple.
Exemplul 1
cursuri.in
1 4 2 2 16 1 3 3 18 1 20
cursuri.out
3
Explicație
O variantă de programare optimă este următoarea:
- în prima sală se vor susține cursurile programate între
[1,3]şi[3,18] - în a doua clasă se susține cursul programat între
[1,20]
Exemplul 2
cursuri.in
2 4 2 5 12 9 18 1 3 1 7
cursuri.out
4
Explicație
Durata maximă pe care o pot avea toate cursurile este 4.
Cursul al treilea se va mări și se va desfășura între [1,5], celelalte se vor micșora. Cursurile vor fi distribuite în cele două săli astfel:
- Sala 1: al treilea și primul profesor programați între
[1,5]respectiv[5,9];
Sala 2: al patrulea și al doilea profesor programați între[1,5]respectiv[9,13];
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 Cursuri:
#include <bits/stdc++.h>
#define nmax 1005
#define inFile "cursuri.in"
#define outFile "cursuri.out"
using namespace std;
struct Interval
{
int a, b;
};
Interval t[nmax];
/// dmax[i] = timpul final al ultimului interval
/// pus in sala i, i=1..K
int d[nmax];
int n, K, op, M;
void Citire()
{
int i;
ifstream fin(inFile);
fin >> op;
fin >> n >> K;
for (i = 1; i <= n; i++)
{
fin >> t[i].a >> t[i].b;
M = max(M, t[i].b - t[i].a);
}
fin.close();
}
inline bool Cmp(const Interval X, const Interval Y)
{
if (X.b == Y.b) return X.a < Y.a;
return X.b < Y.b;
}
void Optiune1()
{
int i, j, p, ans, D;
sort(t + 1, t + n + 1, Cmp);
ans = 0;
for (i = 1; i <= n; i++)
{
/// caut d[p] maxim, p=1..K
/// cat mai aproape de capatul stang al intervalului i
p = 0; D = -1;
for (j = 1; j <= K; j++)
if (d[j] <= t[i].a && d[j] > D)
{
p = j;
D = d[j];
}
if (p != 0)
{
d[p] = t[i].b;
ans++;
}
}
ofstream fout(outFile);
fout << ans << "
";
fout.close();
}
/// returneaza 1 daca toate intervalele (de lungime L)
/// se incadreaza in K clase
int Verifica(int L)
{
int i, j, p;
for (i = 1; i <= n; i++)
t[i].b = t[i].a + L;
for (i = 1; i <= K; i++)
d[i] = 0;
sort(t + 1, t + n + 1, Cmp);
for (i = 1; i <= n; i++)
{
/// caut d[p] minim, p=1..K
p = 1;
for (j = 2; j <= K; j++)
if (d[p] > d[j]) p = j;
if (d[p] <= t[i].a)
d[p] = t[i].b;
else return 0;
}
return 1;
}
void Optiune2()
{
int st, dr, L, sol;
st = 1; dr = M; sol = 0;
while (st <= dr)
{
L = (st + dr) / 2;
if (Verifica(L))
{
sol = L;
st = L + 1;
}
else dr = L - 1;
}
ofstream fout(outFile);
fout << sol << "
";
fout.close();
}
int main()
{
Citire();
if (op == 1) Optiune1();
else Optiune2();
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 
.
Rezolvarea problemei #2044 Cursuri
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2044 Cursuri 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!