2018-09-22-尺取

题目：hihocoder1831
今天参加北京网络赛，AC掉了这一题，当时思路很不清晰，反复思考，前后拖延了一个小时，中间还WA了两次。
下来了再看相关题解，才知道这是一道尺取(PS:很形象)。不过感觉这种算法用处不大，更像是依据具体场合才能抽象出来，不像贪心或者DP，所以，从某种意义上来说，会不会算法也是一种工具，依据具体场合而发挥作用。
相关题目：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;
}