А, кажется, сообразил, в чём фокус.
Наша задача — как можно более рационально распорядиться временем до 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 минут.