AOJ_0112 A Milk Shop
解法
かかる時間が小さいほうから並べて足していくだけでいい。
カンニングしたら、signed int型だとオーバーフローするケースが
あるらしいと分かったので、long longを使う。
コード
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 50000; int time[MAX_N]; int main(){ int n; while(scanf("%d", &n) && n){ for(int i = 0; i < n; i++) scanf("%d", &time[i]); sort(time, time + n); long long sum = 0, res = 0; for(int i = 0; i < n; i++){ sum += res; res += time[i]; } printf("%lld\n", sum); } return 0; }
AOJ_1018も同じ方法で解ける。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 50000; int time[MAX_N]; int main(){ int n; while(scanf("%d", &n) && n){ for(int i = 0; i < n; i++) scanf("%d", &time[i]); sort(time, time + n); long long sum = 0, res = 0; for(int i = 0; i < n; i++){ sum += res; res += time[i]; } printf("%lld\n", sum); } return 0; }