POJ——3061题 Subsequence 尺取法

r囧r小猫 2022-02-16 05:01 213阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;24814</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;10475</td> 
  </tr> 
 </tbody> 
</table>

Description

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.

Input

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.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2
    10 15
    5 1 3 5 10 7 4 9 2 8
    5 11
    1 2 3 4 5

Sample Output

2
    3

## 思路一 ##

算法挑战上的思路是先创建一个结果数组sum1，sum1\[i\]的值为a数组前i项的和

然后从0开始直至后几项相加小于s时结束。期间若有解小于最小解，则更新最小解

代码如下

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int main()
    {
    	int t,n,s;
    	int sum1[100001],a[100005];
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d%d",&n,&s);
    		sum1[0]=0;
    		for(int i=0;i<n;i++){
    			scanf("%d",&a[i]);
    			sum1[i+1]=sum1[i]+a[i]; //sum1数组代表a数组前i项和 
    		}
    		if(sum1[n]<s){  //若所有项相加依旧小于s则无解 
    			printf("0\n");
    			continue;
    		}
    		int minx=n;  //minx标记为最小解 
    		for(int i=0;sum1[i]+s<=sum1[n];i++){   //结束条件为后i至n项相加小于s 
    			int t=lower_bound(sum1+i,sum1+n,sum1[i]+s)-sum1;  //二分查找到满足从i往后数t-i项相加大于s的最小值 
    			minx=min(minx,t-i); //更新最小解 
    		}
    		printf("%d\n",minx);
    	} 
    	return 0; 
    }

## 思路二 ##

首先找到最开始的前几项相加大于s

然后将最靠前的一项减去，若还能大于s，则接着减去当前最靠前一项，直至不大于s，然后在依次加上后面的若干项直至再次大于s

代码如下：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int a[100005],sum1[100005];
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--){
    	    int n,s,sum1=0;
    	    cin>>n>>s;
    	    for(int i=0;i<n;i++){
    	    	   cin>>a[i];
    	    } 
    	    int minx=n+1,left=0,right=0; //minx代表最小解，left代表最靠前的位置，right代表最靠后的位置
    	    for(;;){
    	   	    while(sum1 < s && right < n){  //加至sum1大于s或加至a数组最后一个
    	   	   	    sum1+=a[right++];
    	   	    }
    	   	    if(sum1<s){  //当最后的若干项相加已经不能大于s时跳出for循环
    	   	   	    break;
    	   	    }
    	   	    if(minx>right-left)minx=right-left;   //若此时有比minx还小的解，则更新最小解
    	   	    sum1-=a[left++];  //将最前端的一项减去，
    	    }
    	    if(minx>n)minx=0;
    	    cout<<minx<<endl;
    	} 
    	return 0; 
    }