cf924B

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

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单调递增,于是用双指针扫描即可