3739 - Cafea

Cerința

Într-o cafenea, un barista trebuie să pregătească diverse tipuri de cafea pentru clienți. Fiecare comandă de cafea are un anumit timp de preparare, iar barista dorește să minimizeze timpul total de așteptare al clienților. Sarcina ta este să implementezi un program care să determine ordinea optimă în care barista trebuie să prepare comenzile pentru a minimiza timpul total de așteptare utilizând o metodă greedy.

Date de intrare

Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de comenzi. O listă de n numere întregi reprezentând timpul de preparare pentru fiecare comandă.

Date de ieșire

Pe ecran se va afișa timpul total minim de așteptare al clienților.

Restricții și precizări

• 1 ⩽ n ⩽ 100
• Timpul de preparare pentru fiecare comandă este un număr întreg pozitiv

Exemplu 1

Intrare

4
3 1 4 3

Iesire

23

Exemplu 2

Intrare

3
2 5 1

Iesire

12

Rezolvare

<syntaxhighlight lang="python" line> def citeste_date():

   try:
       n = int(input("Introduceți numărul de comenzi (n): "))
       timpuri = list(map(int, input("Introduceți timpii de preparare, separați prin spațiu: ").split()))
       return n, timpuri
   except ValueError:
       return None, None

def valideaza_date(n, timpuri):

   if not (1 <= n <= 100):
       return False
   if len(timpuri) != n:
       return False
   if not all(isinstance(timp, int) and timp > 0 for timp in timpuri):
       return False
   return True

def calculeaza_timp_minim_asteptare(n, timpuri):

   timpuri.sort()
   timp_asteptare_total = 0
   timp_cumulat = 0

   for timp in timpuri:
       timp_cumulat += timp
       timp_asteptare_total += timp_cumulat

   return timp_asteptare_total

def main():

   n, timpuri = citeste_date()
   
   if n is None or timpuri is None or not valideaza_date(n, timpuri):
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   print("Datele de intrare corespund restricțiilor impuse.")
   timp_minim_asteptare = calculeaza_timp_minim_asteptare(n, timpuri)
   print(timp_minim_asteptare)

if __name__ == "__main__":

   main()

</syntaxhighlight>