Chinaunix首页 | 论坛 | 博客
  • 博客访问: 959542
  • 博文数量: 77
  • 博客积分: 821
  • 博客等级: 军士长
  • 技术积分: 1905
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-23 16:17
个人简介

学校:上海交通大学软件工程 学历:硕士 行业:从事流媒体移动开发 QQ: 412595942 邮箱:yiikai1987910@gmail.com

文章分类

全部博文(77)

文章存档

2016年(4)

2015年(15)

2014年(16)

2013年(12)

2012年(21)

2011年(9)

分类: C/C++

2015-02-28 09:54:49

     我们先来介绍一下尺取法。尺取法,顾名思义,像尺子一样,一块一块的截取。是不是解释的有点让人纳闷~。。没关系,下面我们通过这个题目来体会尺取法的魅力。


题目翻译:

  给定长度为n的数列整数a0,a1,a2,a3 ..... an-1以及整数S。求出综合不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。

 

  限制条件:

    10

    0

    S<10^8

 

这里我们拿第一组测试数据举例子,即 n=10, S = 15, a = {5,1,3,5,10,7,4,9,2,8}

 

   这幅图便是尺取法怎么“取”的过程了。

  整个过程分为4布:

    1.初始化左右端点

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

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

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

 

用尺取法来优化,使复杂度降为了O(n)。

最后,再给一个尺取法的定义以便更好理解:返回的推进区间开头和结尾,求满足条件的最小区间的方法称为尺取法。

以上为网上关于尺取法的原理介绍,还是比较好理解的,邢如蚯蚓的爬动。

直接上代码:

点击(此处)折叠或打开

  1. #include "stdafx.h"
  2. #include <set>
  3. #include <map>
  4. #define MAXN 10
  5. #define S 11
  6. #define min(x,y) (x>y?y:x)
  7. int sequence[MAXN] = {5,1,3,5,10,7,4,9,2,8};

  8. int slove(int sequence[])
  9. {
  10.     int s = 0, t = MAXN , sum = 0 , i = 0;
  11.     int res = MAXN + 1;
  12.     while (1)
  13.     {
  14.         while (sum < S && i < MAXN)
  15.         {
  16.             sum += sequence[i++];
  17.         }
  18.         if (sum < S)
  19.         {
  20.             return res;
  21.         }
  22.         if (res > MAXN)
  23.         {
  24.             printf("not find \n");
  25.             return res;
  26.         }
  27.         res = min(res,(i - s));
  28.         sum -= sequence[s];
  29.         s++;
  30.     }
  31. }

  32. int _tmain(int argc, _TCHAR* argv[])
  33. {
  34.     int res = slove(sequence);
  35.     printf("res is %d\n",res);
  36.     return 0;
  37. }

阅读(15851) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~