Fișierul cheltuieli.in are cel mult 10⁶ linii, fiecare linie conţinând câte trei numere naturale din intervalul [1,10²], reprezentând, în această ordine, date despre câte o achiziţie: tipul produsului cumpărat, numărul de produse de acest tip cumpărate, respectiv prețul unui astfel de produs la acel moment. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.
Se cere să se afişeze pe ecran cea mai mare sumă cheltuită pentru toate produsele de același tip, precum și numărul de tipuri de produse pentru care s-a obținut această sumă.
Proiectati un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul cheltuieli. in are conținutul alăturat, se afişează pe ecran: 26 2 (s-a cheltuit suma maximă 26 pentru produsele de tipul 1 și 4: 26 = 16 • 1 + 5 • 2 = 1 • 10 + 2 • 8)
cheltuieli.in:
4 1 10
1 16 1
4 2 8
2 1 5
1 5 2
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficienta acestuia.
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
Răspunsuri la întrebare
a) Programul citeste din fisier triplete de numere
si calculeaza suma fiecarui tip de produs in vectorul s,
in acelasi timp afland si suma maxima din vectorul s.
Vectorul s se va parcurge apoi pentru a se contoriza numarul de aparitii
al sumei maxime in variabila k.
Algoritmul este eficient din punct de vedere al timpului de executare
deoarece numerele din fisier sunt citite o singura data
iar vectorul s este reparcurs o singura data
doar pentru contorizarea aparitiilor sumei maxime
rezultand o complexitate liniara O(n) unde n este numarul de triplete din fisier.
b) #include <iostream>
#include <fstream>
using namespace std;
int main() {
int x, y, z, a[100]={0}, k=0, smax=-1;
ifstream f("cheltuieli.in");
while (f>>x>>y>>z) {
s[x]=s[x]+y*z;
if (s[x]>smax) {
smax=s[x];
}
}
f.close():
for (int i=1; i<=100; i++) {
if (s[x]==smax) {
k++;
}
}
cout<<smax<<' '<<k;
return 0;
}