顾客的等待时间

题目描述

超市的收银处有 n 位顾客在排队等着付款，他们的编号依次为 1,2， …， n。由于每个顾客所购的商品不同，因此付款时所需的等待时间也就不一样。为了节省顾客的等待时间，收银员有权利安排顾客的付款顺序，让所有顾客总等待时间最少。 给出这 n 个顾客单独付款所需的时间。而根据顾客不同的付款顺序，每个顾客总等待时间是不一样的，收银员想知道所有顾客总等待时间最少是多少？

样例说明：一共4位顾客付款，假设收银员安排的付款顺序是1122。 第1个顾客不需要等待，等待时间为0；第2个顾客开始等第1位顾客结账，第2个顾客的等待时间是1，总等待时间为0+1=1；第3个顾客的等待时间是前2位顾客的结账时间，需要等1+1=2，总等待时间为1+2=3；第4个顾客的等待时间是前3位顾客的结账时间，是1+1+2=4，总等待时间为4+3=7；所有顾客的等待时间就是7。

输入格式

共2行，第一行为正整数n，表示排队的人数，1≤n≤100。 第二行n个由空格分隔的正整数，分别为这n个人单独付款所需的时间，每位顾客单独付款所需的时间≤150。

输出格式

共1行1个数，表示所有顾客的最少等待时间。

4
1 2 1 2

7

提示

样例说明：一共4位顾客付款，假设收银员安排的付款顺序是1122。 第1个顾客不需要等待，等待时间为0；第2个顾客开始等第1位顾客结账，第2个顾客的等待时间是1，总等待时间为0+1=1；第3个顾客的等待时间是前2位顾客的结账时间，需要等1+1=2，总等待时间为1+2=3；第4个顾客的等待时间是前3位顾客的结账时间，是1+1+2=4，总等待时间为4+3=7；所有顾客的等待时间就是7。

来源

童程童美