CF 957C Three-level Laser (二分)

Three-level Laser

题意

输入一个n，m，n代表接下来有n个数字（从小到大），

接下来从n个数字中选3个数字i，j，k（i<j<k），

使得k-j/k-i 最大，且（k-i）<=m。(n<1e5)

思路

开头直接写，j=1开始遍历，要让值最大，i=j-1,（必定），k为可允许内最大的值。

用for找k，会T，于是改用二分，输出用.15f（精度限制，double到.6）。

看！代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;
int a[N];
int main()
{
    int n,U;
    scanf("%d%d",&n,&U);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    double res=-1.0;
    for(int i=1;i<=n-2;i++) 
    {
        int t1=a[i],t2=a[i+1],up=U+t1;
        int k=upper_bound(a+1,a+1+n,up)-a-1;
        if(k<i+2) continue;
        res=max(res,(a[k]-t2*1.0)/(a[k]-t1));
    }
    printf("%.15f\n",res);
    return 0;
}