SRM 645 Div2 Medium ConnectingCars

問題

SRM 645 - TopCoder Wiki

1つのレールの上に複数の車が並んでいる. 各車はpositions[i]に位置し,そこから右方向にlengths[i]の長さだけ車体が伸びている. いま,この車を隙間なく並びたい,各車体の位置を左右どちらかに1だけ移動するコストが1とすると, 目的を達成する最小コストを求める問題.

解答

  • 一列に並べた時の最左の位置を決めると,コストは自明に導ける.
  • 証明はできないが,位置を左から右に移動した時のコストを考えるとピークは一つだと思う.
  • ということは二分探索(本当はternary search)で最左の位置を求めることで問題を解くことが出来る.

解説を見ると,最適解の内,いずれかの車を全く動かさずに良い解が必ず存在するらしい. そうかもなと思うけど,解説を呼んでも確信は持ててない.

class ConnectingCars
{
public:
  long long cost(long long target, vector<int> & positions, vector<int> lengths) {
    long long cost = 0;
    for (int i = 0; i < positions.size(); i++) {
      cost += abs(target - positions[i]);
      target = target + lengths[i];
    }
    return cost;
  }
  long long minimizeCost(vector <int> positions, vector <int> lengths)
    {
      long long low = 0;
      long long high = 10000000000;
      long long mid1, mid2;
      int n = positions.size();
      int i, j;
      // sort
      for (i = 0; i < n; i++) {
        for (j = i+1; j < n; j++) {
          if (positions[i] > positions[j]){
            swap(positions[i], positions[j]);
            swap(lengths[i], lengths[j]);
          }
        }
      }
      while (low <= high) {
        mid1 = (2*low + high) / 3;
        mid2 = (low + 2*high + 2) / 3;
        // cout << "low=" << low << " high=" << high << endl;
        // cout << "mid1=" << mid1 << " mid2=" << mid2 << endl;
        if (cost(mid1, positions, lengths) < cost(mid2, positions, lengths)) {
          high = mid2-1;
        }else {
          low = mid1+1;
        }
      }
      return cost((low + high) / 2, positions, lengths);
    }
};