二分Three-level Laser

我就是我 2022-05-27 04:26 115阅读 0赞

题目链接：http://codeforces.com/problemset/problem/924/B

/*题解报告：题意要求(a[k]-a[j])/(a[k]-a[i])的最大值，
    易知当a[j]和a[i]挨着的时候 上式会取的最大值，
    即转化为求(a[k]-a[j])/(a[k]-a[j-1])的最大值，
    要保证(a[k]-a[j])/(a[k]-a[j-1])式取得最大值就要使分子取得最大值，
    即a[k]-a[j]取最大，
    还有一个约束条件就是a[k]-a[j-1]<=U,j/i一定，a[k]越大越好，所以二分查找 使a[k]-a[j]取得最大。
    */
    #include<stdio.h>
    int main()
    {
        int n,u;
        double  a[100005];
        while(scanf("%d%d",&n,&u)!=EOF)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%lf",&a[i]);
            }
            double max=-1;
            for(int i=1;i<n-1;i++)
            {
                if(a[i+1]-a[i-1]>u)
                {
                    continue;
                }
                int l=i,r=n-1;
                while(l<r)
                {
                    int mid=(l+r+1)/2;
                    if(a[mid]-a[i-1]>u)
                    {
                        r=mid-1;
                    }
                    else
                    {
                        l=mid;
                    }
                }
                double div=(a[r]-a[i])/(a[r]-a[i-1]);
                if(div>max)
                {
                    max=div;
                }
            }
            if(max==-1)
            {
                printf("-1\n");
            }
            else
            {
                printf("%.10f\n",max);
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关二分查数+二分模板

定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。如果数组中不存在该元

妖狐艹你老母/ 2023年09月30日 11:06/ 0 赞/ 39 阅读

相关【MTK AF】Acce/Gyro/PD/Laser Driver Check

一.Data collection steps数据收集阶段 1.把手机固定在一定距离并设置高对比度 2.执行ADB指令 3.打开相机然后拍照片 4.切换到录像

偏执的太偏执、/ 2022年09月05日 12:53/ 0 赞/ 45 阅读

相关 PE 144 Investigating multiple reflections of a laser beam （计算几何）

Investigating multiple reflections of a laser beam Problem 144 In laser physics, a

谁借莪１个温暖的怀抱￠/ 2022年07月15日 08:19/ 0 赞/ 70 阅读

相关二分练习

think: 1感觉自己的二分查找时候有点繁琐了，判断条件用的有点多，一开始没有发现如果查找的最后一组数据即a\[i\] = a\[j\] = a\[mid\] = x的时

刺骨的言语ヽ痛彻心扉/ 2022年07月12日 11:45/ 0 赞/ 85 阅读

相关 CodeForces - 609D (二分！二分！)

D. Gadgets for dollars and pounds time limit per test 2 seconds memory limit per test

╰半夏微凉°/ 2022年05月29日 10:59/ 0 赞/ 262 阅读

相关二分Three-level Laser

题目链接：http://codeforces.com/problemset/problem/924/B /题解报告：题意要求(a[k]-a[j])/(a[k]-a[i

我就是我/ 2022年05月27日 04:26/ 0 赞/ 116 阅读

相关二分查找

/ 有序数组递归二分查找，定位值的下标 @param arr 目标数组 @param start 起始下标

喜欢ヅ旅行/ 2022年04月06日 14:22/ 0 赞/ 351 阅读

相关 Facebook开源工具包LASER，支持93种语言

> 为了加速自然语言处理（NLP）在更多语言上进行零样本迁移，Facebook 扩展并增强了LASER（Language-Agnostic SEntence Represent

女爷i/ 2022年02月22日 01:13/ 0 赞/ 280 阅读

相关二分查找

int search2( int array\[\], int n, int v) \{ int left, right, middle;

心已赠人/ 2021年12月20日 16:07/ 0 赞/ 157 阅读

相关二分模板

二分模板中点的值满足要求 while (l < r) { int mid = l + r >> 1; if(check(m

短命女/ 2021年11月23日 14:14/ 0 赞/ 311 阅读