Codeforces Round #364 (Div. 2) D. As Fast As Possible __ binary search、方程 或解方程 直接解出答案

Source

Codeforces Round #364 (Div. 2)

My Solution

binary search、方程

1、binary search、方程

每个pupil 坐车的时间相同、走路的时间相同、总时间相同。

所以 l = 0, r = INF;

对于 每个答案 x，验证总时间 cnt <= x，即车跑的总时间要小于等于 总的总时间

t1 + t2 == x            // t1 为每个pupil 走路的总时间， t2 为每个pupil坐车的总时间，每个pupil 都必须且只做一次车

v1 * t1 + v2 * t2 == l(路程)    //求出 t2

-------------------------------->

<----------------

-------------------------------->

<----------------

-------------------------------->

......               ......

-------------------------------->
就像图中所示每次 -->的时间都是 t2， 每次 <--的时间都是 dt，

(t2 + dt) * v1 == t2 * v2 - dt * v2；        //求出 dt

求出车子跑的总时间 cnt = t2 + (t - 1) *(dt + t2)         //其中 t表示车子载人的总次数， t = n / k， 当 t * k < n 时 t++

这样 cnt <= x 则 时间还可以更短 r = x， 否则时间不够 l = x；

此外 eps = 1e-6的时候Accepted了，最开始 eps取了1e-12导致一些特殊数据时无法跳出while循环 而TLE，如果直接解方程就基本上误差非常小了(请看方法2)

复杂度 O(logn)

2、解方程 直接解出答案

其实有以上的这些方程组可知，最后可以化成关于 x 的一次不等式

t1 + t2 == x

t = n / k， 当 t * k < n 时 t++

v1 * t1 + v2 * t2 == l(路程)    //求出 t2

(t2 + dt) * v1 == t2 * v2 - dt * v2

cnt = t2 + (t - 1) *(dt + t2)

cnt <= x

当 cnt 无限趋向于 x时， 求出的x就是答案， 而且精确度比二分法高的多。

ans = (s + ((t - 1) * ((v2  - v1) / (v1 + v2) + 1))*s) / (v2 + ((t - 1) * ((v2  - v1) / (v1 + v2) + 1)) * v1);

复杂度 O(1)

1、Source code for binary search、方程

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;
const int INF = 1e9 + 7;
const double eps = 1e-6;

int n, k, t;
double s, v1, v2, t1, t2, cnt;
//t1 + t2 == x; v1*t1 + v2*t2 == s
inline bool check(double x)
{
    t2 = (s - x * v1) / (v2 - v1);
    //then check whether this t2 is possible.
    cnt = t2;
    //for(int i = 2; i <= t; i++){ cnt += (t - 1)*((v2 * t2 - v1 * t2) / (v1 + v2) + t2); //} if(cnt > x) return false;
    else return true;

}

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> s >> v1 >> v2 >> k;
    t = n / k;
    if(t * k < n) t++;
    double l = 0, r = INF, x;
    while(l + eps < r){
        x = (l + r) / 2;
        if(check(x)) r = x;
        else l = x;
        //cout << l << " " << r << endl;
    }
    cout << fixed << setprecision(10) << min(x, s / v1) << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

2、Source code for 解方程 直接解出答案

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;
const int INF = 1e9 + 7;
const double eps = 1e-6;

int n, k, t;
double s, v1, v2, t1, t2, cnt;
//t1 + t2 == x; v1*t1 + v2*t2 == s
/*
inline bool check(double x)
{
    t2 = (s - x * v1) / (v2 - v1);
    //then check whether this t2 is possible.
    cnt = t2;
    //for(int i = 2; i <= t; i++){ cnt += (t - 1)*((v2 * t2 - v1 * t2) / (v1 + v2) + t2); //} if(cnt > x) return false;
    else return true;

}
*/

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 3;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> s >> v1 >> v2 >> k;
    t = n / k;
    if(t * k < n) t++;
    /*
    double l = 0, r = INF, x;
    while(l + eps < r){
        x = (l + r) / 2;
        if(check(x)) r = x;
        else l = x;
        //cout << l << " " << r << endl;
    }
    */
    double k = (t - 1) * ((v2  - v1) / (v1 + v2) + 1);
    double ans = (s + k*s) / (v2 + k * v1);
    cout << fixed << setprecision(10) << min(ans, s / v1) << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx