POJ 3061(尺取法入门)

? 题目地址:http://poj.org/problem?id=3061 ?

  尺取法:就是用双指针l,r来圈定一个区间,在区间满足一定条件的时候我们就可以使用尺取法.

  尺取法题目特征:有一个区间,左指针指向a(下标),右指针指向b(下标),我们有一个区间条件

就这道题而言是区间和>=s,此时我们需要把左指针右移一个单位,如果区间和还是>=s,那么这

个时候右指针可能在b上或者b的右边都满足题意.

  总之如果我们需要用一个区间来截取某一个条件的时候我们就可以使用尺取法来做题用尺取法

做题也就是用两个指针去维护一个区间.使区间不断右移来达到我们所需要的答案.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring> 
using namespace std;

typedef long long LL;
const int Max_n=100005;
int a[Max_n];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(a,0,sizeof(a));
        int n,s;
        scanf("%d%d",&n,&s);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int l=0,r=0,ans=Max_n,sum=a[0];
        if(a[0]>=s){//先把第一个加上,然后去扩大右端点. 
            printf("1\n");
            continue;
        } 
        while(l<=r&&r<n){
            r++;
            sum+=a[r];
            while(sum>=s){//直到<s为止 
                ans=min(ans,r-l+1);
                sum-=a[l];
                l++;
            }
        }
        printf("%d\n",ans==Max_n?0:ans);
    } 
    return 0;
}   
           

转载于:https://www.cnblogs.com/zut-syp/p/10560634.html