題目：hihocoder1831
今天參加北京網(wǎng)絡(luò)賽，AC掉了這一題，當時思路很不清晰，反復思考，前后拖延了一個小時，中間還WA了兩次。
下來了再看相關(guān)題解，才知道這是一道尺取(PS:很形象)。不過感覺這種算法用處不大，更像是依據(jù)具體場合才能抽象出來，不像貪心或者DP，所以，從某種意義上來說，會不會算法也是一種工具，依據(jù)具體場合而發(fā)揮作用。
相關(guān)題目：POJ-3061
hihocoder1831:

#include<stdio.h>

#define N 1000001

long long c=0,a[N]={0},b[N<<1]={0};

int main()
{
    int T,n,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%lld",&n,&c);
        for(i=1,a[0]=0;i<=n;i++)
            scanf("%lld",a+i);
        for(i=1,b[0]=0;i<=n;i++)
        {
            scanf("%lld",b+i);
            b[i]=a[i]-b[i];
            b[i+n]=b[i];
        }
        for(i=1,n<<=1;i<=n;i++)
            b[i]+=b[i-1];
        int cnt;
        for(cnt=0,i=1,n>>=1;cnt<n&&i<n+cnt+1;)
        {
            if(c+b[i]-b[cnt]<0)
            {
                cnt++;
                if(b[cnt]>0)
                    i=cnt+1;
            }
            else
                i++;
        }
        if(cnt==n)
            cnt=-2;
        printf("%d\n",cnt+1);
    }
    return 0;
}

POJ-3061:

#include<stdio.h>

#define N 100000

int main()
{
    int n,T;
    long long s,a[N];
    scanf("%d",&T);
    while(T--)
    {
        int i,j,cnt;
        long long sum;
        scanf("%d%lld",&n,&s);
        for(i=0;i<n;i++)
            scanf("%lld",a+i);
        for(j=0,i=0,cnt=n+1,sum=a[0];i<n&&cnt!=1;)
        {
            if(sum<s)
                sum+=a[++i];
            else
            {
                if(cnt>i-j+1)
                    cnt=i-j+1;
                sum-=a[j++];
            }
        }
        printf("%d\n",cnt==n+1?0:cnt);
    }
    return 0;
}