每日一题-Subsequence（前缀和+尺取法）（复习）-白红宇

每日一题-Subsequence（前缀和+尺取法）（复习）

阅读量：315 次

发布时间：2019-03-04

本文共 526 字，大约阅读时间需要 1 分钟。

在这里插入图片描述

大意是：

给一个整数数列，找这个数列的子序列的和大于给定数值s的最短序列长度。

思路：

尺取法应用：

1.把子序列看成一个蚯蚓，当子序列和小于s时，头向前伸，直到子序列和大于等于s时就停止前伸，并记录长度。

2.尾部前伸，直到序列和小于数值s停止前伸，并记录长度。

然后再伸头，一直循环下去。

3.每次记录长度时更新结果，取最小值。

#include
   
    using namespace std;typedef long long LL;int num[100005];void solve(){
   	int n,s;	cin>>n>>s;	for(int i=1;i<=n;i++)	{
   		cin>>num[i];	}	LL sum=0;	int len=n+1;	for(int l=1,r=1;r<=n+1;)	{
   		if(sum>=s)		{
   			len = min(r-l,len);			sum -= num[l]; 			l++;//			if(l>=r) break;		}		if(sum
    
     >t;	while(t--)	{
   		solve();	}	return 0; }

转载地址：http://xnrq.baihongyu.com/

你可能感兴趣的文章