[Codeforces Round472C] Three-level Laser

[题目链接]

        https://codeforces.com/contest/957/problem/C

[算法]

        二分 

        注意精度问题

        时间复杂度 ：O（NlogN)

[代码]

       

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-18;
const int MAXN = 1e5 + 10;

int n,m;
int a[MAXN];
double ans;
bool ok;

template <typename T> inline void read(T &x)
{
    int f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}
template <typename T> inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x/10);
    putchar(x%10+'0');
}
template <typename T> inline void writeln(T x)
{
    write(x);
    puts("");
}

int main() 
{
        
        read(n); read(m);
        for (int i = 1; i <= n; i++) read(a[i]);
        ans = 0.0; ok = false;
        for (int i = 1; i <= n; i++)
        {
                int l = i + 1 , r = n , pos = -1;
                while (l <= r)
                {
                        int mid = (l + r) >> 1;
                        if (a[mid] - a[i] <= m)
                        {
                                pos = mid;
                                l = mid + 1;
                        } else r = mid - 1;
                }
                if (pos == -1 || pos == i + 1) continue;
                if ((1.0 * (a[pos] - a[i + 1]) / (a[pos] - a[i]) - ans) > eps)
                        ans = 1.0 * (a[pos] - a[i + 1]) / (a[pos] - a[i]);
                ok = true;        
        }
        if (!ok) printf("-1
");
        else printf("%.10lf
",ans);
        
        return 0;
    
}