cf924B

链接

题意

        给你长度为n的单调增数组a[]，以及一个u
        让你找一个三元组 i<j<k且a[k]-a[i]<u
        最大化(a[k]-a[j])/(a[k]-a[i])

题解

        我们考虑枚举i，j
        显然当i，j固定后这个值整体上是小于1的，
        所以k越大越好，整体值越大
        
        然后我们发现，当i,j固定后,k的值只与i有关，因为a[k]-a[i]<u
        也就是说不管我们枚举的i和j如何，k只与i有关，不妨设k=f(i)
        
        我们现在考虑枚举i，于是k的值也确定了，为f(i)
        
        这时候，j显然越小越好，于是j=i+1最优
        
        第一个做法出来了：
            枚举i，则j=i+1，根据a[k]<a[i]+u，可以二分出k
        第二个做法：
            枚举i，则j=i+1，容易证明f(i)关于i单调递增，于是用双指针扫描即可