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

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

阅读量：319 次

发布时间：2019-03-04

本文共 521 字，大约阅读时间需要 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/

你可能感兴趣的文章

Nature封面：只低一毫米，时间也会变慢！叶军团队首次在毫米尺度验证广义相对论...