A - Subsequence (算法 二分 )
算法 二分 Subsequence
2023-09-11 14:22:48 时间
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements
of the sequence, the sum of which is greater than or equal to S.
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case,
separated by intervals. The input will finish with the end of file.
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5
2 3
using namespace std;int main(){int u;int sum[MAX+22];int ans;int n,s;scanf("%d",&u);while(u--){scanf("%d %d",&n,&s);scanf("%d",&sum[0]); //注意这个地方 for(int i=1; i<n; i++){scanf("%d",&sum[i]);sum[i]+=sum[i-1]; } if(sum[n-1]<s) { printf("0\n"); continue; } ans =n; int pos; for(int i=n-1; i>=0; i--) { if(sum[i]<s) break; pos=upper_bound(sum,sum+n,sum[i]-s)-sum; ans=min(ans,i-pos+1); } printf("%d\n",ans); } return 0;}
相关文章
- 程序员学算法必备网站之一:VisuAlgo
- 学弟学妹们,别瞎学算法了,跟着师兄来看懂这道链表题!
- (《机器学习》完整版系列)第9章 聚类——9.2 k均值算法、学习向量量化算法(在类标记的指导下进行聚类)
- 决策树算法之特征工程-特征提取
- hihoCoder #1122 : 二分图二•二分图最大匹配之匈牙利算法
- 扩展欧几里得算法
- C#,数据检索算法之二分搜索(Binary Search)的源代码
- 查找算法--线性查找、二分查找和三分查找的原理及适用场景
- python实现二分查找算法
- 【C语言】详解:折半查找(二分查找算法)
- [算法]选择排序
- Shiro教程之四 散列算法和凭证配置
- 【Unity3D进阶4-2】Unity3D A*寻路算法
- 算法模板(一)(相关话题:二分搜索)
- 各种群体寻优算法的比较
- stm32工程和算法分享(4)--单击按键之传统方式消抖
- 编程算法 - 两个升序列的同样元素 代码(C)
- 数据结构与算法分析-索引
- 矿Java开发学习之旅------>Java排序算法经典的二分法插入排序
- Java实现二分查找算法
- 王道数据结构 (8) 树的遍历算法及递归代码实现
- leetcode算法203.移除链表元素