《挑战程序设计竞赛》3.2.1 常用技巧-尺取法 POJ3061 3320 2566 2739 2100(1)

本文主要是介绍《挑战程序设计竞赛》3.2.1 常用技巧-尺取法 POJ3061 3320 2566 2739 2100(1),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

POJ3061

http://poj.org/problem?id=3061

题意

给定长度为n的整数数列以及整数S,求出总和不小于S的连续子序列的长度的最小值,如果解 不存在,输出0.

思路

如果用二分法
先求出sum[i],从第1个数到第i个数的区间和,每次固定一个开始查找的起点sum[i], 然后采用二分查找找到 sum[i] + S 的位置,区间长度即为(末位置-(起始位置-1)),用ans保存过程中区间的最小值。时间复杂度 O(nlogn)。
但如果用尺取法会将复杂度大大降低:
反复地推进区间的开头和末尾,来求满足条件的最小区间的方法称为尺取法。
主要思想为:当a1, a2 , a3 满足和>=S,得到一个区间长度3,那么去掉开头a1, 剩下 a2,a3,判断是否满足>=S,如果满足,那么区间长度更新,如果不满足,那么尾部向后拓展,判断a2,a3,a4是否满足条件。重复这样的操作。
时间复杂度 O(n)。
尺取法的深入理解:
当一个区间满足条件时,那么去掉区间开头第一个数,得到新区间,判断新区间是否满足条件,如果不满足条件,那么区间末尾向后扩展,直到满足条件为之,这样就得到了许多满足条件的区间,再根据题意要求什么,就可以在这些区间中进行选择,比如区间最长,区间最短什么的。

代码

Source CodeProblem: 3061       User: liangrx06
Memory: 632K        Time: 63MS
Language: C++       Result: Accepted
Source Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;const int N = 1e5;int main(void)
{int t, n, s;int a[N];cin >> t;while (t--) {cin >> n >> s;for (int i = 0; i < n; i ++)scanf("%d", &a[i]);int ans = n+1;int l = 0, r = 0, sum = 0;while (true) {while

这篇关于《挑战程序设计竞赛》3.2.1 常用技巧-尺取法 POJ3061 3320 2566 2739 2100(1)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/868682

相关文章

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

python常用的正则表达式及作用

《python常用的正则表达式及作用》正则表达式是处理字符串的强大工具,Python通过re模块提供正则表达式支持,本文给大家介绍python常用的正则表达式及作用详解,感兴趣的朋友跟随小编一起看看吧... 目录python常用正则表达式及作用基本匹配模式常用正则表达式示例常用量词边界匹配分组和捕获常用re

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧