本文主要是介绍《挑战程序设计竞赛》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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!