Advertisement

算法题:子序列和问题(poj-3061),使用尺取法解决

阅读量:

题目所对应的网络地址为:POJ-3061

在这里插入图片描述

题意:给定一个数列,要求找出一个最短的连续子序列,使得其元素之和不小于S。

问题分析:

  1. 首先,该数列中所有元素均为正整数。当某一子序列的和达到或超过S时,无需再将右端点向右移动,因为继续扩展子序列的长度必然会导致长度增加。
  2. 因此,在子序列和小于S的情况下,应将右端点向右移动;而当子序列和达到或超过S时,则应将左端点向右移动。
  3. 若在右端点移动至最末端后,子序列的总和仍小于S,则结束枚举过程。
    本题所涉及的区间和具有明显的趋势性特征:呈现单调变化特性。因此,根据题目要求可以较为简便地进行求解。不过,在实际应用前需要对区间的前缀和进行预处理计算。

问题所在点
0x3f3f3f3f 是以0x开头的十六进制常量,对应的十进制数值为1061109567。换算成二进制形式则为 00111111 00111111 00111111 00111111。
在算法竞赛中,我们通常会设定一个常量来表示“无穷大”的概念。

全部评论 (0)

还没有任何评论哟~