UVALive 2678 子序列

我会带着你远行 2022-09-30 03:43 15阅读 0赞

**[题目链接: https://vjudge.net/problem/34000/origin][https_vjudge.net_problem_34000_origin]**

**题意 :** 有n(10<n<=100 000)个正整数a\[i\] (a\[i\]<10 000) 组成的一个序列.给定整数S,求长度最短的连续序列,使他们的和大于或等于S(S <1e9).

**Sample Input**

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

**Sample output**

2

3  
  
**分析:**  
只求和,可以先更新得到和序列,此时枚举左右端点(i,j)还是超时.注意到和序列是递增的,对于每个右端点我们要找到最大满足条件(s\[j\] - s\[i\] >= S)可以二分得到i,此时时间复杂度O(nlog(n))  
可以进一步优化,若s\[j\]对应的i为x,那么s\[j+1\]对应的i一定大于等于x,也就说满足条件的i也是递增的,可以接着上次的i计算这次的i,也就最多只需找n次i;时间复杂度为O(n);

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int a[100100];
    
    int main()
    {
        int n, s;
        while(scanf("%d%d", &n, &s) != EOF)
        {
            a[0] = 0;
            for(int i = 1; i <= n; i++)
            {
                scanf("%d", &a[i]);
                a[i] += a[i - 1];
            }
            int i = 1;
            int ans = n + 1;
            for(int j = 1; j <= n; j++)
            {
                if(a[i - 1] > a[j] - s) continue;
                while(a[i] <= a[j] - s) i++;
                ans = min(ans, j - i + 1);
            }
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= n; j++)
                {
                    for(int k = j; )
                }
            }
            printf("%d\n", ans == n + 1 ? 0 : ans);
        }
        return 0;
    }

[https_vjudge.net_problem_34000_origin]: https://vjudge.net/problem/34000/origin

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关判断子序列

392. 判断子序列 > 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 > 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对

忘是亡心i/ 2024年04月03日 09:07/ 0 赞/ 65 阅读

相关判断子序列

判断子序列给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。请你判断 a 序列是否为 b 序列的子序列。

红太狼/ 2024年03月30日 12:03/ 0 赞/ 81 阅读

相关序列自动机：判断子序列

序列自动机：判断子序列文章目录序列自动机：判断子序列序列自动机问题：思路：

我就是我/ 2023年10月06日 19:40/ 0 赞/ 41 阅读

相关 Subsequence 子序列

Subsequence 191221 > 答案思路英文题翻译为中文 Title 题目： A sequence of N positive integers (

悠悠/ 2022年12月29日 09:11/ 0 赞/ 147 阅读

相关子序列子数组问题 Leetcode

子序列子数组问题 [53. 最大子序和][53.] 给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

灰太狼/ 2022年10月31日 10:45/ 0 赞/ 238 阅读

相关 UVALive 2197

题意：n个点，m条边，还有一个k，给出每条边的信息，让你选择一些边，使得这些边组成的图里面，每个点只属于k个回路上，问最小的费用。分析：如果每个点都只在k个回路上，那

布满荆棘的人生/ 2022年10月02日 12:00/ 0 赞/ 20 阅读

相关 UVALive 2678 子序列

[题目链接: https://vjudge.net/problem/34000/origin][https_vjudge.net_problem_34000_origin]

我会带着你远行/ 2022年09月30日 03:43/ 0 赞/ 16 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1,

骑猪看日落/ 2022年07月13日 01:56/ 0 赞/ 144 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1,

拼搏现实的明天。/ 2022年07月12日 02:48/ 0 赞/ 182 阅读

相关上升子序列

Problem Description 一个只包含非负整数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列\{a1, a2,

ゞ浴缸里的玫瑰/ 2022年05月16日 01:45/ 0 赞/ 150 阅读