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;
}