केबलों को जोड़ें
आपके पास
n केबल हैं, जिनकी लंबाई दी हुई है। इन सभी को जोड़कर एक बड़ा केबल बनाना आपका लक्ष्य है। यदि आपके पास लंबाई x और y वाले दो केबल हैं और आप उन्हें जोड़ना चाहते हैं, तो इसकी लागत x + y होगी। इन दोनों केबलों को जोड़ने के बाद नया केबल x + y लंबाई का बन जाता है।सवाल यह है कि सभी केबलों को जोड़ने में आपको कुल कितना न्यूनतम खर्च करना पड़ेगा?
इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ ) है, जो केबलों की संख्या दर्शाता है।अगली पंक्ति में स्पेस द्वारा अलग किए गए (1 ≤ ≤ ) दिए गए हैं, जो इन केबलों की लंबाई हैं।
आउटपुट
सभी केबलों को जोड़ने में आने वाला न्यूनतम कुल खर्च प्रिंट करें।
उदाहरण
Input | Output |
5
1 2 3 6 2 | 30 |
व्याख्या
- Connect 1 and 2 ⇒ pay 3 ⇒ 3 3 6 2
- Connect 2 and 3 ⇒ pay 5 ⇒ 5 3 6
- Connect 3 and 5 ⇒ pay 8 ⇒ 6 8
- Connect 6 and 8 ⇒ pay 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB