Re[12]: Время черепахи
От: Кодт Россия  
Дата: 03.07.15 09:54
Оценка:
А, кажется, сообразил, в чём фокус.

Наша задача — как можно более рационально распорядиться временем до t[n-1].
Найти такую минимальную задержку на старте w, при которой черепаха достигает последнего цветка к моменту F(w) >= t[n-1].
Если F(w) < t[n-1], это значит, что она вынуждена ждать на финише. Почему бы это же самое не подождать на старте?

F(w) имеет косо-ступенчатый вид — примерно вот так
F
|         /
|        |
|________|________ t[n-1]
|        |
|        |
|        |__________ нам нужно сюда
|       /:
|      / :
|     |  :
|     | наткнулись ещё на 1 цветок, +1*d
|    /   :
|   / до следующего цветка - опять финиш отодвигается со стартом
|  |     :
|  |     :
|  |     :
|  | наткнулись на 2 цветка, сразу затормозили на них, +2*d
| / отодвигаем финиш синхронно со стартом... dF/dw = 1
|/       :
|        :
| даже при нулевой задержке мы можем съесть пару цветков...
|        :
|        :
0--------+------ w

F(w)>=t[n-1] (недолёт-перелёт)
|
|        +------
|        |
0--------+------ w


Простой, хотя и медленный (O(n*log(t[n-1]))) способ найти нижнюю границу — это реализовать функцию F(w) и бисекцией подобрать.
minutes F(minutes w) {
  for (int i=0; i<n; ++i) { // включая последний цветок
    if (t[i] < w)
      w += t[i];
  }
  return w;
}

minutes solve() {
  minutes tlast = t[n-1];
  minutes wmin = 0, wmax = tlast; // верхняя граница выставлена с избытком
  assert(F(wmax) >= tlast);
  while(wmax-wmin > epsilon) {
    minutes wmed = (wmin+wmax)/2;
    if (F(wmed) >= tlast)
      wmax = wmed;
    else
      wmin = wmed;
}


Очевидно, что при большом t[n-1] мы заставим черепаху мысленно побегать! Единственная радость, что в сутках только 1440 минут.
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.