Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem B - Subway

Subway trains are meant to move people as quickly, safely, and comfortablyas possible from station to station. Although the train drivers' unionsmay not agree, computer operated trains accomplish these goals moreeffectively than human operated trains. You are to determinethe optimal control strategy to move the train from one station to anotherwithin the constraints imposed by safety and comfort considerations,as well as the physical limitations of the train itself.

The parameters to the problem are all positive integers not greater than 1000.

• d - the distance between stations, in metres
• m - the maximum allowable speed of the train, in metres/sec
• a - the maximum absolute acceleration of the train, in metres/sec²
• j - the maximum absolute jerk, in metres/sec³

The train must be completely stopped at each station and must move in onedirection at speeds not exceeding m. Acceleration can be positive (forward) or negative (backwards)but its absolute value must not exceed a.The last parameter, jerk, is the rate of change of acceleration in either direction. That is, acceleration cannot increase or decrease at greaterthan this rate. This parameter prevents toppling the standing passengers.

There are several test cases. For each test case, standard input has asingle line with d, m, a, j. For each test case, standardoutput should contain a single line giving the minimum time in seconds,to the nearest 0.1 second, required to move between the stations.

Sample Input

1000 70 20 1

Output for Sample Input

31.7

---

題目描述：
在四者限制下，問時間消耗最少。兩站距離 d，且其中最大速度不超過 m,
最大加速度絕對值不超過 a, 最大加速度變化量不超過 j。
從一站到另一站時，速度皆為零，同時加速度也都為零。
求最少時間花費到達下一站。
// 其實我不知道怎麼稱呼 j 的中文，這裡暫且用加速度變化量表示之

題目解法：
明顯地會發現加速度變化量 J(t) = j, -j, 0 這三種可能情況而已。
但要討論加速度會不會達到最大值 a, 以及速度會不會到達最大值 m,
在最佳解中，加速度盡可能大，但不超過 a 時。同時積分的面積不超過 m,
最後得到上方兩種圖形，但因為左右對稱，只考慮一半的距離，同時也是一半的消耗時間。

令一開始 a(t) = jt 的時刻 0~t1, 其後以 a(t) = jt1 的時刻為 t1~t2,
=> 則最後所耗的時間是 "t1 + t2 + 剩餘距離/當前最高速度"

第一種情況：讓速度達到最高速 m, 但加速度沒達到 a
1) 達到最高速後，跑的距離不超過 d,
在 0~2*t1, m = (jt1 * 2*t1)/2 = jt1*t1 => 藉此得到 t1 = sqrt(m/j);
此時已經走了 1/6*j*t1*t1*t1 /*t = 0~t1*/ + 5/6*j*t1*t1*t1 /*t =t1~2t1*/
剩餘時間 = 剩餘距離 / m
2) 在達到最高速前，跑的距離超過 d,
t1 要縮小，必須跟去移動的距離決定 t1
=> 1/6*j*t1*t1*t1 + 5/6*j*t1*t1*t1 = d/2 => j*t1*t1*t1 = d/2
=> t1 = pow(d/2/j, 1/3)

第二種情況：讓加速度達到最大限 a, 但速度不超過 m
1) 達到最大加速度後，會維持 t2-t1 的時間的不變加速度,
在其速度達到最上限 m 的情況，及此時不超過距離 d
=> 有用最大速度再走一段時間
2) 反之，在達到最大上限速度前，走的距離超過 d,
因此考慮將 t2 往前移動(靠近 t1)

之所以不在第二種情況的 2) 中考慮 t1 往前調整，是因為不會有最佳解。

最後，積分的部分我就懶得打了，請原諒我。







#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {
    /*freopen("in.txt", "r+t", stdin);
    freopen("out2.txt", "w+t", stdout);*/
    double D, M, A, J;
    double d;
    while(scanf("%lf %lf %lf %lf", &D, &M, &A, &J) == 4) {
        d = D/2;
        double t1, t2, v3;
        double d1, d2, d3;
        double ret = 1e+60;
        double l = 0, r = M, m;
        m = M;
        t1 = A/J;
        if(2*t1*A/2 > m) {
            t1 = sqrt(m/J);
            t2 = t1;
        } else {
            t2 = (m-A*t1)/A+t1;
        }
        v3 = J*t1*t1/2 + J*t1*(t2-t1) + J*t1*t1/2;
        d1 = J*t1*t1*t1/6;
        d2 = (J*t1*t1 + J*t1*(t2-t1))*(t2-t1)/2;
        d3 = (J*t1*t1/2 + J*t1*(t2-t1))*t1 + J*t1*t1*t1/2 - J*t1*t1*t1/6;
        if(d1+d2+d3 > d) {
            t1 = pow(d/J, 1/3.0);
            t2 = t1;
            v3 = J*t1*t1/2 + J*t1*(t2-t1) + J*t1*t1/2;
            d1 = J*t1*t1*t1/6;
            d2 = (J*t1*t1 + J*t1*(t2-t1))*(t2-t1)/2;
            d3 = (J*t1*t1/2 + J*t1*(t2-t1))*t1 + J*t1*t1*t1/2 - J*t1*t1*t1/6;
            if(t1*J > A) {//d1+d2+d3 = d => at2^2 + bt2 + c = 0
                t1 = A/J;
                double a, b, c;
                a = J*t1/2, b = J*t1*t1/2, c = -d;
                t2 = ((-b)+sqrt(b*b-4*a*c))/(2*a);
                v3 = J*t1*t1/2 + J*t1*(t2-t1) + J*t1*t1/2;
                d1 = J*t1*t1*t1/6;
                d2 = (J*t1*t1 + J*t1*(t2-t1))*(t2-t1)/2;
                d3 = (J*t1*t1/2 + J*t1*(t2-t1))*t1 + J*t1*t1*t1/2 - J*t1*t1*t1/6;
                ret = min(ret, t1+t2+(d-d1-d2-d3)/v3);
            } else
                ret = min(ret, t1+t2+(d-d1-d2-d3)/v3);
        } else {
            ret = min(ret, t1+t2+(d-d1-d2-d3)/v3);
        }
        //printf("%lf %lf %lf %lf\n", t1, t2, d3, d1+d2+d3);

        printf("%.1lf\n", ret*2);
    }
    return 0;
}
/*
52 1 72 63
52.3
*/