UVa 10440 Ferry Loading II
問題概要
n台車を詰める船がある。
m台の車がある岸に到着する時刻が与えられる。
t分、対岸の岸まで船が移動するのにかかる。
最速の運び方を
最小の手数で求めよ。
解法
貪欲
ある最適解があったとする。
最後の船が満タンまで積んでいない場合、それより前の車をできるだけたくさんその船で運んでも
かかる時間は変わらない。
つぎにその最後の船を取り除いて、残った船での運び方を考えても、
できるだけあとの船で運ぶようにしてもかかる時間はかわらない。
よって貪欲的に後ろから船に乗せていって良い。
また、貪欲的に乗せると最小の手数であることは自明である。
よって、後ろから貪欲法でとける。
ソース
#include<iostream> #include<algorithm> #include<vector> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) #define ALL(C) (C).begin(),(C).end() #define FOR(it,o) for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it) using namespace std; int main(){ int T; cin >> T; rep(tc, T){ int n, t, m; cin >> n >> t >> m; vector<int> car(m); rep(i, m){ cin >> car[i]; } vector<int> res; for(int i = m-1; i>= 0; i-=n){ res.push_back(car[i]); } reverse(ALL(res)); int nowTime = 0; FOR(it, res){ nowTime = max(nowTime + t * 2, *it + t*2); } cout << nowTime - t << ' ' << res.size() << endl; } return 0; }