UVA live 2678 - Subsequence

简介: 关于这个题目,有多种的解法,如果枚举起点和终点,时间复杂度为O(n^3),但如果我们用一个数组B把一段数的和存起来,B[i] = sum(a[1].....a[i])。这样就可以把时间复杂度降到O(n^2)。

题目链接


题意:

   有n个正整数组成的序列,给定一个整数s,求长度最短的连续序列,使他们的和大于或等于s。


   关于这个题目,有多种的解法,如果枚举起点和终点,时间复杂度为O(n^3),但如果我们用一个数组B把一段数的和存起来,B[i] = sum(a[1].....a[i])。这样就可以把时间复杂度降到O(n^2)。


   还有更好的方法,因为B数组是递增的,我们只需要枚举终点,然后二分查找起点即可,时间复杂度进一步降到O(n*logn),但我们可以继续优化,由于B[i]-s是递增的,枚举的起点也是递增的,换句话说,满足条件的位置也是递增的,因此我们可以怎么写


代码:


//2013-05-21-20.37
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int b[100005];
int main()
{
    int n, s;
    while (scanf("%d %d", &n, &s) != EOF)
    {
        b[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &b[i]);
            b[i] += b[i-1];
        }
        int ans = n+1, i = 1;
        for (int j = 1; j <= n; j++)
        {
            if (b[i-1] > b[j]-s)
                continue;
            while (b[i] <= b[j]-s)
                i++;
            ans = min(ans, j-i+1);
        }
        printf("%d\n", ans == n+1?0:ans);
    }
    return 0;
}


这样就将时间复杂度降到O(n)了。

前两种代码我就不写了,具体参见刘汝佳训练指南49页。

目录
相关文章
uva live 3516 - Exploring Pyramids
点击打开链接 题意:给出一棵多叉树,每个结点的任意两个子节点都有左右之分。从根节点开始,每次尽量往左走,走不通就回溯,把遇到的字母顺序记录下来,可以得到一个序列。
751 0
uva 10716 - Evil Straw Warts Live
点击打开链接uva 10716 题目意思:  给定一个字符串求出最小需要几步交换(只有相邻才能够交换)能够变成回文串,如果不能构成回文串就输出Ipossbile 解题思路:    1:贪心 2:对于给定的字符串,如果要使得转化...
996 0
|
API C++ Windows
【Live555】Live555 Windows下使用VS2017编译教程
【Live555】Live555 Windows下使用VS2017编译教程
【Live555】Live555 Windows下使用VS2017编译教程
|
数据建模 C++ Windows
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板
live555开发笔记(一):live555介绍、windows上msvc2017编译和工程模板