UVA 12697 Minimal Subarray Length
Minimal Subarray Length
This problem will be judged on UVALive. Original ID: 6609
64-bit integer IO format: %lld Java class name: Main
You are given an integer sequence of length N and another value X. You have to find a contiguous subsequence of the given sequence such that the sum is greater or equal to X. And you have to find that segment with minimal length.
Input
First line of the input file contains T the number of test cases. Each test case starts with a line containing 2 integers N (1 ≤ N ≤ 500000) and X (−109 ≤ X ≤ 109). Next line contains N integers denoting the elements of the sequence. These integers will be between −109 to 109 inclusive.
Output
For each test case output the minimum length of the sub array whose sum is greater or equal to X. If there is no such array, output ‘-1’.
Sample Input
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
Sample Output
3
-1
3
解题:先求和。维护一个队列,下标单调,值也单调。对于i,j.如果sum[i] <= sum[j] && i > j ,那么i肯定比j好。去掉j.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
LL sum[maxn] = {};
int n,x,inc[maxn];
int main() {
int t,i,lt,rt,ans;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&x);
for(i = ; i <= n; i++){
scanf("%lld",sum+i);
sum[i] += sum[i-];
}
lt = ;
inc[] = rt = ;
ans = n+;
for(i = ; i <= n; i++){
while(lt < rt && sum[i] <= sum[inc[rt-]]) rt--;
inc[rt++] = i;
while(lt + < rt && sum[i] - sum[inc[lt]] >= x){
ans = min(ans,i-inc[lt]);
lt++;
}
}
ans == n+?puts("-1"):printf("%lld\n",ans);
}
return ;
}
最新文章
- mongodb安装及基础命令
- mysql按汉语拼音首字母排序
- 【转】C#程序打包安装部署之添加注册表项
- Ubuntu下安装可视化SVN客户端Rabbitvcs
- The secret code
- IntellijIdea中常用的快捷键
- JAVA多线程synchronized详解
- Linux shell入门基础(八)
- LeetCode_Combination Sum II
- iOS中UISearchBar(搜索框)使用总结
- 移动端开发(四):swiper.js
- linux下操作gpio寄存器的方法
- Java 第三章 选择结构
- java--银行业务调度系统
- URI和URL的区别 【转】
- 清北学堂4.28Day1(重大更新详见贪心例一)
- vs2019 cdkey 秘钥
- session与cookie的区别是什么?如果客户端禁用了cookie功能,将会对session有什么影响?
- chrome浏览器下载内容存放位置
- C#集合类型大揭秘
热门文章
- SQL Server 添加描述
- bzoj Strange Way to Express Integers【excrt】
- bzoj [Usaco2010 Hol]cowpol 奶牛政坛【树链剖分】
- android_app c++框架
- 基于ASP.Net Core开发一套通用后台框架记录-(总述)
- [C++ STL] 常用算法总结
- [转]ASP.NET MVC Domain Routing
- Javascript DOM 编程艺术(第二版)读书笔记——基本语法
- python自动化--模块操作之re、MySQL、Excel
- jdbc 实现分页