TopCoder SRM 676 Div2 250 FarmvilleDiv2(参加)

n個の植物がある. それぞれ time[i]秒成長するのにかかる.

<p>
  cost[i]をbudgetのなかから支払うと、1秒成長を早めることができる.
</p>

<p>
  time, cost, budgetが与えられる. 植物を育てることのできる時間の最小値をかえせ.
</p>

costを昇順にソーティング. costの低い順に時間を計算

<ul class="org-ul">
  <li>
    budgetがまだあるときは、total時間は加算しない.
  </li>
  <li>
    budgetがないときは、time分 total時間を加算する.
  </li>
</ul>

timeとcostをインデックスをそろえながらソーティングするよい方法が思い つかなかったので、自力でソーティングアルゴリズムを実装した。

<p>
  なにかよい方法はないものか。他の人の解答をみて研究することにする.
</p>

<p>
  [sourcecode language="python" title="" ] class FarmvilleDiv2: def insertion_sort(self, time, cost, N): for i in range(1, N): v1 = time[i] v2 = cost[i] j = i - 1 while j >= 0 and cost[j] > v2: time[j + 1] = time[j] cost[j + 1] = cost[j] j -= 1 time[j + 1] = v1 cost[j + 1] = v2 return time, cost
</p>

<p>
  def minTime(self, time, cost, budget): time = list(time) cost = list(cost) time, cost = self.insertion_sort(time, cost, len(cost))
</p>

<p>
  ret = 0
</p>

<p>
  for t, c in zip(time, cost): for i in range(t): if budget - c >= 0: budget -= c else: ret += 1
</p>

<p>
  return ret [/sourcecode]
</p>