首页 > UVALive2678:Subsequence

UVALive2678:Subsequence

UVALive2678:Subsequence

题目大意

给定一个数组A和一个整数S。求数组A中，连续且之和不小于S的连续子序列长度最小值。

要求复杂度:Ο(n)

Solution

用变量L表示所选区间最左端下标，用变量R表示所选区间最右端下标，用变量sum表示所选区间的和。从左到右扫描一遍数组，如果sum比S小，则右移R，扩大所选区间，从而增大sum。通过不断的右移L达到遍历整个数组的目的。

Note

  1. 当解不存在时需要输出0。不知道为什么题目中并没有明确的指出这一点，但如果不加以考虑一定会WA。
  2. 数组中单个元素不超过int类型的表示范围，但子序列之和有可能超过，因此需要使用long long类型

AC-Code(C++)

Time:33ms

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 100000 + 10;/** 刘汝佳 训练指南 P48*/int A[maxn];int main(int argc, const char * argv[]) {//    freopen("input.txt", "r", stdin);int N,S;while(scanf("%d %d",&N,&S)==2){for(int i=0;i

转载于:https://www.cnblogs.com/irran/p/UVALive2678.html

更多相关：

  • PCL点云分割（2）

    关于点云的分割算是我想做的机械臂抓取中十分重要的俄一部分，所以首先学习如果使用点云库处理我用kinect获取的点云的数据，本例程也是我自己慢慢修改程序并结合官方API 的解说实现的，其中有很多细节如果直接更改源程序，可能会因为数据类型，或者头文件等各种原因编译不过，会导致我们比较难得找出其中的错误，首先我们看一下我自己设定的一个场景，...

  • PCL点云配准（2）

    /* 使用正态分布变换进行配准的实验 。其中room_scan1.pcd room_scan2.pcd这些点云包含同一房间360不同视角的扫描数据 */ #include #include #include #include

  • PCL点云变换与移除NaN

    #include #include #include #include ...

  • PCL滤波介绍(3)

    #include #include #include #include #include #include...

  • PCL滤波介绍（2）

    #include #include #include #include int main (int argc,...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • LeetCode 1021:Remove Outermost Parentheses

    C语言 char * removeOuterParentheses(char * S){int len = strlen(S);int j = 0;int sum = 0;for(int i = 0; i < len; i++){if (S[i] == '('){sum += 1;}else if (S[i] == ')'){sum...

  • Codeforces Round #563 (Div. 2)/CF1174

    Codeforces Round #563 (Div. 2)/CF1174 CF1174A Ehab Fails to Be Thanos 其实就是要(sumlimits_{i=1}^n a_i)与(sumlimits_{n+1}^{2n}a_i)差值最大，排一下序就好了 CF1174B Ehab Is an Odd...

  • pat乙级1049

    浮点型乘整型和整型乘浮点型结果不同，不知为什么。 1 double sum = 0.0; 2 for (int i = 0; i < n; i++) 3 { 4 cin >> a[i]; 5 sum += a[i] * (i + 1) * (n - i); 6 } 7 printf("%.2f", sum); 提...

©2024 11GX.COM