AOJ 0112 A Milk Shop

404 Not Found

単純明快な問題・・・かと思いきや小さい落とし穴があった問題。正答率の低さはそれが原因だろう。

だって問題の性質は404 Not Foundと全く同じなのに、こっちの正答率は83%だから。(まあ答える層のレベルが違うんだろうけど)

単純に待ち時間を昇順ソートすれば最適解になるのはすぐ分かる。まあここはほとんどの人がたどり着くけど、落とし穴が一つ。問題文を良く読むと、

ただし、お客さんは10,000人以下で1人あたりに要する時間は 60 分以下とします。

60分以内で1万人ってイメージ的には少ないのだけど、実際計算がモロ総和の総和的な感じなんで最悪のケースの場合どうなるかというと、

1万人居て、全員60分の場合、2,999,700,000(30億くらい)

とまあ、結構でかい数となります。で、この約30億はsigned int型だと溢れます。負の数に突入しちゃいます。これがWAの原因です。嫌らしい数値設定だ。

unsigned型で定義するかlong longしましょう。一回Wrong出した。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	unsigned n,m,sum,wait;
	vector<unsigned> v;
	while(cin >> n && n){
		v.clear();
		sum = wait = 0;
		for(int i=0;i<n;i++){
			cin >> m;
			v.push_back(m);
		}
		sort(v.begin(),v.end());
		for(int i=0;i<n;i++){
			sum += wait;
			wait += v[i];
		}
		cout << sum << endl;
	}
}

訴　訟　確　定　の瞬間である。