文档章节

poj 3061 尺取法

Loi_DL
 Loi_DL
发布于 2016/11/03 07:41
字数 568
阅读 5
收藏 0
Subsequence
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 12078   Accepted: 5055

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

2
3

Source




题目大意: 给你一个正整数序列 让你求不小于s的最小子序列长度。

尺取法

ps:尺取法是需要序列符合单调性的。

反复地推进区间的开头和末尾

,来求满足条件的最小区间的方法称为尺取法。

主要思想为:当a1,  a2  , a3 满足和>=S,得到一个区间长度3,那么去掉开头a1,   剩下 a2,a3,判断是否满足>=S,如果满足,那么区间长度更新,如果不满足,那么尾部向后拓展,判断a2,a3,a4是否满足条件。重复这样的操作。

个人对尺取法的理解:

当一个区间满足条件时,那么去掉区间开头第一个数,得到新区间,判断新区间是否满足条件,如果不

满足条件,那么区间末尾向后扩展,直到满足条件为之,这样就得到了许多满足条件的区间,再根据题

意要求什么,就可以在这些区间中进行选择,比如区间最长,区间最短什么的。这样跑一遍下来,时间

复杂度为O(n)。

代码:
#include <iostream>
#include <cstdio>
using namespace std;
int a[100050];
int main()
{
int t;
cin>>t;
while (t!=0)
{

t--;
int n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0,q=1,e=1,ans=n+1;

for(;;)
{
while(e<=n&&sum<s)
{
sum+=a[e];
e++;
}
if(sum<s)
break;
ans=min(ans,e-q);
sum-=a[q];
q++;
}
if(ans==n+1)
cout<<0<<endl;
else 
cout<<ans<<endl;
}
return 0;
}

© 著作权归作者所有

Loi_DL
粉丝 0
博文 60
码字总数 48692
作品 0
莱芜
私信 提问
BZOJ:2038: [2009国家集训队]小Z的袜子(hose)(莫队算法模板)

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2038 解题心得: 第一次接触莫队算法,很神奇,很巧妙。莫队算法主要就是用来解决多次询问时维护区间内的信息。维护区间信息第...

GoldenFingers
2018/08/06
0
0
LeetCode-Longest Substring Without Repeating Characters

作者: 一字马胡 时间:2018-04-02 题目描述 分析与解决 题目的意思是说,给定一个字符串,找出不含有重复字符的最长子串的长度。题目中举了几个例子,比如对于字符串“abcabcbb”来说,最长...

一字马胡
2018/04/02
0
0
LeetCode 滑动窗口法总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89066140 1. 介绍 滑动窗口法,也叫...

dby_freedom
04/07
0
0
POJ 1067 取石子游戏

取石子游戏 Description 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取...

angel_kitty
2017/02/19
0
0
poj1067:取石子游戏(Betty定理)

传送门 题意: 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量...

qq_35649707
2017/12/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

面试爱奇艺,竟然挂在第5轮……

今天给大家分享我曾经在爱奇艺的面试,过程还是比较有意思的,可以给大家一些参考 <br> 聊骚阶段 嗲妹妹:你好,我是爱奇艺的HR,我们正在招聘运维开发岗位,请问您最近有在看工作机会吗? ...

上海小胖
27分钟前
0
0
Jenkins系列_插件安装及报错处理

进入Jenkins之后我们可以进行插件的安装,插件管理位于以下模块: 发现上面报了一堆错误,是因为插件的依赖没有安装好,那么这一节,就先把这些错误解决掉吧。解决完成后,也就基本会使用插件...

shzwork
今天
2
0
mysql mysql的所有查询语句和聚合函数(整理一下,忘记了可以随时看看)

查询所有字段 select * from 表名; 查询自定字段 select 字段名 from 表名; 查询指定数据 select * from 表名 where 条件; 带关键字IN的查询 select * from 表名 where 条件 [not] in(元素...

edison_kwok
昨天
9
0
解决多线程并行加载缓存问题(利用guava实现)

依赖 com.google.guava:guava:20.0 import com.google.common.cache.Cache;import com.google.common.cache.CacheBuilder;import java.util.concurrent.ExecutionException;import j......

暗中观察
昨天
4
0
利用VisualVM 内存查看

准备工作,建几个测试类。等下就是要查看这几个类里面的属性 package visualvm;public class MultiObject { private String str; private int i; MultiObject(String str...

冷基
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部