尺取法知识点讲解

2024-04-20 16:12
文章标签 讲解 知识点 取法

本文主要是介绍尺取法知识点讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、固定长度的情况:

最小和(sum)  

输入N个数的数列,所有相邻的M个数的和共有N-M+1个,求其中的最小值。

输入格式

第1行,2个整数N,M,范围在[3…100000],N>M。

第2行,有N个正整数,范围在[1…1000]。 

输出格式

1个数,表示最小和。 

输入/输出例子1

输入:

6 3

10 4 1 5 5 2

输出:

10

【方法一】:枚举开始点,计算连续M个数的和,求出最小值。

程序如下:

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-m+1;i++){long long s=a[i];for(int j=i+1;j<=i+m-1;j++)s+=a[j];mins=min(s,mins);}cout<<mins;return 0;
}

时间复杂度是o(n*m)如果数据量太大会超时。

微信截图_20231028101330.png

如图1所示,如果以第一个数开始计算也就是图1红色部分。

s1=a[1]+a[2]+a[3]   

如图2所示,如果以第二个数开始计算也就是图2蓝色部分

         s2=a[2]+a[3]+a[4]

对比图1和图2,公式s1和s2,我们会发现,如果以第一个数开始枚举m=3个数的和,和以第二个数开始枚举m个数的和,重复了a[2]+a[3],也就是说,我们第一个数开始枚举完m个数的和后,完全不用从第二个数再重新枚举,只要在s1的基础上保留重复部分a[2]+a[3],去掉左边的a[1],加入右边的a[4],让长度保持m个。

s1=a[1]+a[2]+a[3]  

s2=s1-a[1]+a[4]

尺取法:就如尺子一样,利用两个指针L和R,L代表左边枚举开始点,,R代表枚举结束点,s代表区间L到R的和,如果此时L到R刚好m个数,也就是R-L+1==m,那么找到一个长度为m的和,后面只要把s=s-a[L]+a[R+1],L++,R++,让其长度保持为m。

【程序如下】:

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int L=1,R=1;R<=n;R++){s+=a[R];if(R-L+1==m){mins=min(mins,s);s=s-a[L];L++;}}cout<<mins;return 0;
}

二、不固定长度情况

无标题.png

【程序如下】:

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,a[100005];
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];int minL=n+1;for(int L=1,R=1;R<=n;R++){s+=a[R];while(s>=m){minL=min(minL,R-L+1);s=s-a[L];L++;}}cout<<minL;return 0;
}

三、总结

尺取法是一种线性算法,也是一种高效的枚举区间的方法。

记 (l,r)两个端点为一个序列内以l为起点的最短合法区间,如果r随l的增大而增大的话,我们就可以使用尺取法。

具体的做法是:

    1.初始化左右端点

    2.不断扩大右端点,直到满足条件

    3.如果第二步中无法满足条件,则终止,否则更新结果

    4.将左端点扩大1,然后回到第二步

因为r随 l增大而增大,所以 r只有 n次变化的机会,所以时间复杂度为O(n)。

这篇关于尺取法知识点讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/920716

相关文章

RabbitMQ消费端单线程与多线程案例讲解

《RabbitMQ消费端单线程与多线程案例讲解》文章解析RabbitMQ消费端单线程与多线程处理机制,说明concurrency控制消费者数量,max-concurrency控制最大线程数,prefe... 目录 一、基础概念详细解释:举个例子:✅ 单消费者 + 单线程消费❌ 单消费者 + 多线程消费❌ 多

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

Java进程CPU使用率过高排查步骤详细讲解

《Java进程CPU使用率过高排查步骤详细讲解》:本文主要介绍Java进程CPU使用率过高排查的相关资料,针对Java进程CPU使用率高的问题,我们可以遵循以下步骤进行排查和优化,文中通过代码介绍... 目录前言一、初步定位问题1.1 确认进程状态1.2 确定Java进程ID1.3 快速生成线程堆栈二、分析

javascript fetch 用法讲解

《javascriptfetch用法讲解》fetch是一个现代化的JavaScriptAPI,用于发送网络请求并获取资源,它是浏览器提供的全局方法,可以替代传统的XMLHttpRequest,这篇... 目录1. 基本语法1.1 语法1.2 示例:简单 GET 请求2. Response 对象3. 配置请求

Java Stream.reduce()方法操作实际案例讲解

《JavaStream.reduce()方法操作实际案例讲解》reduce是JavaStreamAPI中的一个核心操作,用于将流中的元素组合起来产生单个结果,:本文主要介绍JavaStream.... 目录一、reduce的基本概念1. 什么是reduce操作2. reduce方法的三种形式二、reduce

CSS引入方式和选择符的讲解和运用小结

《CSS引入方式和选择符的讲解和运用小结》CSS即层叠样式表,是一种用于描述网页文档(如HTML或XML)外观和格式的样式表语言,它主要用于将网页内容的呈现(外观)和结构(内容)分离,从而实现... 目录一、前言二、css 是什么三、CSS 引入方式1、行内样式2、内部样式表3、链入外部样式表四、CSS 选

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++