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