AOJ0112 A Milk Shop

問題リンク A Milk Shop

• 解法

i番目のお客さんは0〜i-1番目のお客さんの牛乳を注ぎきる時間の合計だけ待つ必要があります。最初の方にもの凄く注ぐのに時間のかかる人がいると、多くの人を長く待たせることになるので良くないことが分かります。最適なのは注ぐ時間が短い順にすることです。この問題はintだとオーバーフローするケースがあるのでlongにしないとWAを食らいます。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//A Milk Shop
public class AOJ0112 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int[] a = new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			Arrays.sort(a);
			long s = 0;
			long t = 0;
			for(int i=0;i<n;i++){
				s += t;
				t += a[i];
			}
			System.out.println(s);
		}
	}
}