《挑战程序设计竞赛》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

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java

springboot项目中常用的工具类和api详解

《springboot项目中常用的工具类和api详解》在SpringBoot项目中,开发者通常会依赖一些工具类和API来简化开发、提高效率,以下是一些常用的工具类及其典型应用场景,涵盖Spring原生... 目录1. Spring Framework 自带工具类(1) StringUtils(2) Coll

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S