Problemi 115

Kërkesa

Colit i pëlqen të luaj me numrat dhe sot po bën një lojë të tillë:

Në një listë me numra A zgjedh dy numra të njëpasnjëshëm. Më të madhin prej tyre e heq nga lista, dhe kështu gjatësia e listës zvogëlohet me 1. Kostoja e këtij veprimi është sa më i vogli prej tyre. Këtë veprim e përsërit deri sa në listë të ketë mbetur vetëm 1 numër, dhe gjen shumën e kostove për të gjitha veprimet.

Sa është vlera më e vogël e kësaj shume?

Referenca: https://www.codechef.com/problems/MNMX

Shembull

$ cat input.txt
2
2
3 4
3
4 2 5

$ python3 prog.py < input.txt
3
4

Në rastin e parë mund të kryejmë vetëm një veprim. Ky veprim fshin numrin 4 nga lista dhe e ka koston 3 (që është edhe kostoja e përgjithshme).

Në rastin e dytë mund të zgjedhim në fillim dyshen 4 2, ku fshihet numri 4 dhe kostoja e veprimit është 2, pastaj mund të zgjedhim dyshen 2 5, ku fshihet numri 5 dhe kostoja e veprimit është 2. Kostoja e përgjithshme është 4.

Zgjidhja 1

for _ in range(int(input())):
    n = int(input())
    l = map(int, input().split())

    # gjejmë numrin më të vogël të listës
    m = l[0]
    for a in l:
        if a < m:
            m = a

    print(m*(n - 1))

Sqarime

Meqenëse mund të zgjedhim një çift numrash çfarëdo, ne na intereson që gjithmonë të zgjedhim numrin më të vogël të listës dhe një numër tjetër pranë tij. Në këtë rast numri tjetër do hiqet nga lista dhe kostoja e veprimit do jetë sa numri më i vogël. Duke zgjedhur gjithmonë numrin më të vogël ne minimizojmë koston totale.

Meqenëse gjithsej kryhen (n - 1) veprime të tilla, kostoja totale është sa prodhimi i numrit më të vogël me (n - 1).

Zgjidhja 2

for _ in range(int(input())):
    n = int(input())
    l = map(int, input().split())
    print(min(l)*(n - 1))