算法进阶指南二分章节的两道题

A.题意:给定个数为N的数列,从中挑一些不小于L的连续子段,求这些子段当中的数平均值最大是多少?

思路:二分平均值转化为判定。我们直接去求这个>=L的子段当中的最大平均值比较难求。所以我们可以用二分的方法枚举mid,然后在判定这个mid是否合法。

判定方法为,是否存在一个长度大于L的连续子段它的平均值>=mid。如果不存在,说明以mid为平均值取大了。则取r=mid。

对平均值的处理有一种特殊方法,另每一个数都减去mid,则判定方法就转化为是否存在一个长度>=L的连续子段,使得每个数的和非负(最大的都>=0,则 一定存在)。

求某一连续子段的方法,利用前缀和来求解,eg sum[ i ] - sum [ j ]就是求  j 到 i 的连续子段和

另外用双指针来求>=L的区间的最大和。因为要保证长度是大于L的 所以i要从L开始往后递增,而  j  从   i-L  开始往前递减, sum[  i ]  -  sum [ j ]就保证了一个大于L的区间。但是由于i 从L往后每递增一个, j 的可选择空间也就增加一个,j的初始空间只有一个选择,而这道题判定方法问存不存在,所以要求我们求连续子段的最大的和,于是我们只需要保存前  i - L 当中最小的那个前缀和就可以了。

下面上代码:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e5+6;
const double eps=1e-6;
int n,L;
double cow[maxn];
double sum[maxn];
double b[maxn];

bool check(double ave)
{
    for(int i=1;i<=n;i++)
        b[i]=cow[i]-ave;

        sum[0]=0;
        for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+b[i];

        double ans=-1e10;
        double min_v=0;
        for(int i=L;i<=n;i++)
        {
            min_v=min(min_v,sum[i-L]);
            ans=max(ans,sum[i]-min_v);
        }
        if(ans>=0)
        return true;
        else
        return false;
}

int main()
{
    cin>>n>>L;
    for(int i=1;i<=n;i++)
    //scanf("%lf",&cow[i]);
    cin>>cow[i];

    double l=0,r=2000;
    while(r-l>eps)
    {
        double mid=(r+l)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }

    printf("%d\n",(int)(r*1000));
    return 0;
 } 

原文地址:https://www.cnblogs.com/rainyskywx/p/10349568.html

时间: 02-02

算法进阶指南二分章节的两道题的相关文章

二分查找算法(递归与非递归两种方式)

首先说说二分查找法. 二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回1,失败返回对应的数组下标. 采用非递归方式完成二分查找法.java代码如下所示. /* * 非递归二分查找算法 * 参数:整型数组,需要比较的数. */ public static int binarySearch(Integer[]srcArray,int des){ //第一个位置. int low=0; //最高位置.数组长度-1,因为下标是从0开始的. int h

算法初学者指南

摘自网络,对于这个训练计划,我只能膜拜,~ 第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15 分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Floyd.Dijstra,BellmanFord) 2. 最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘.判线段相交.然后写个凸包. 6.BFS.DFS,同时熟练hash表(

算法——基础篇——二分查找

     二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.     首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

HDU 4004 The Frog&#39;s Games(基本算法-贪心,搜索-二分)

The Frog's Games Problem Description The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The

【算法拾遗】二分查找递归非递归实现

转载请注明出处:http://blog.csdn.net/ns_code/article/details/33747953 本篇博文没太多要说的,二分查找很简单,也是常见常考的查找算法,以下是递归非递归的实现. 非递归实现: /* 非递归实现,返回对应的序号 */ int BinarySearch(int *arr,int len,int key) { if(arr==NULL || len<1) return -1; int low = 0; int high = len-1; while(l

服务端开发入门与进阶指南

建议:尽量用 google 查找技术资料.有问题在 stackoverflow 找找,大部分都已经有人回答.多看官方的技术文档.ibm developerworkers 的文章质量整体上有保障.平时花一些时间在 github 上阅读优秀项目源码.入门(1-2 个月)目标:参与简单的项目开发.技能:掌握 Java.经典的<Java 核心技术:卷1 基础知识>(或者<Java 编程思想>)必看,跳过其中的图形和 applet 章节.习惯查阅 Java API Doc.为了保证代码的质量

二分查找的两种实现方式(JAVA)

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功. 条件是:1.必须

算法题16 二分查找及相关题目

二分查找思想就是取中间的数缩小查找范围,对应不同的题目变形,在取到中间数mid确定下一个查找范围时也有不同,左边界有的low=mid+1,也可能low=mid,右边界有的high=mid-1,也有可能high=mid. 对于一个排序数组来说二分查找的时间复杂度是O(logn) 1. 二分查找法 1 int BinarySearch(int arr[],int len,int target) 2 { 3 if (arr==NULL||len<=0) 4 throw std::exception(&qu

Git 进阶指南(git ssh keys / reset / rebase / alias / submodule )

在掌握了基础的 Git 使用 之后,可能会遇到一些常见的问题.以下是猫哥筛选总结的部分常见问题,分享给各位朋友,掌握了这些问题的中的要点之后,git 进阶也就完成了,它包含以下部分: 如何修改 origin 仓库信息 如何配置 git ssh keys 如何撤销修改 遇到冲突了怎么解决 git stash / alias / submodule 的使用问题等 问:如何修改 origin 仓库信息? 1.添加 origin 仓库信息 git remote add origin <git仓库地址>

性能测试进阶指南——基础篇之磁盘IO

本文旨在帮助测试人员对性能测试常用指标做一个简单的讲解,主要包括CPU.内存.磁盘和网络带宽等系统资源,本文仅仅局限于Linux系统,Windows Server系统暂不做考虑. 使用iostat分析IO性能 对于I/O-bond类型的进程,我们经常用iostat工具查看进程IO请求下发的数量.系统处理IO请求的耗时,进而分析进程与操作系统的交互过程中IO方面是否存在瓶颈. 下面通过iostat命令使用实例,说明使用iostat查看IO请求下发情况.系统IO处理能力的方法,以及命令执行结果中各字