codeforces 957C Three-level Laser【二分】

题目大意：给你一个n个数的递增的序列，从中找到 Ei ,Ej ,Ek 其中 i<j<k $i<j<k$ 使得 Ek−EjEk−Ei $\frac{Ek-Ej}{Ek-Ei}$最大，并且 Ek-Ei<=u 数据范围 n<1e5 Ei<1e9 u<1e9

分析：通过观察可知，当i,j最接近时，并且距离k越远越大，我们可以知道 j=i+1 ，因此只要确定了i 就可以确定j,那么我们就可以枚举每个i 然后二分找到K值即可

#include <bits/stdc++.h>
using namespace std;
int n,u;
const int maxn=1e5+40;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef long long ll;
int a[maxn];
int main()
{
    scanf("%d%d",&n,&u);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    double ans=0;
    for(int i=1;i<=n-2;i++)
    {
        int x=a[i];
        int y=a[i+1];
        int k=upper_bound(a+1,a+1+n,x+u)-(a+1);
        //cout<<k<<endl;
        int t=a[k];
        //cout<<t<<endl;
        ans=max(ans, 1.0*(t-y)/(t-x)*1.0);
    }
    if(ans==0)printf("-1\n");
    else
    printf("%.9lf",ans);
    return 0;
}