LA 6609 - Minimal Subarray Length

题意：给出一个数组，要求求出最小的子序列满足子序列和大于等于X

代码如下：

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

typedef long long ll;

int rec[500005];

int main()
{
  //  freopen("data.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,x;
        scanf("%d%d",&n,&x);
        for(int i=0;i<n;++i)
        {
            scanf("%d",&rec[i]);
        }
        if(x<=0)
        {
            bool c=false;
            for(int i=0;i<n;++i)
            {
                if(rec[i]>=x){c=true;break;}
            }
            if(c)printf("1\n");
            else printf("-1\n");
            continue;
        }
        int ans=1000000000;
        ll sum=0;
        int start=0;
        for(int i=0;i<n;++i)
        {
     //       cout<<i<<' '<<start<<endl;
            sum=sum+rec[i];
            if(sum<=0)
            {
                sum=0;
                start=i+1;
            }
            if(sum>=x)
            {
//                while(sum>x)
//                {
//                    if(sum-rec[start]<x)break;
//                    sum=sum-rec[start];
//                    start++;
//                }//在数组中可能有负数，导致用这种方法减的时候出错
                int tmp=0;
                for(int j=i;j>=0;--j)
                {
                    if(tmp+rec[j]>=x)
                    {
                        start=j;
                        break;
                    }
                    tmp+=rec[j];
                }
                ans=min(ans,i-start+1);
            }
        }
        if(ans>500001)printf("-1\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}
           

题目数据很弱。。导致上面投机取巧的办法也过了

O(n)复杂度的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int a[500005];
ll sum[500005];

int main()
{
//freopen("data.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,x;
        scanf("%d%d",&n,&x);
        ll maxn=-10000000000;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a[i]);
            if(i)
                sum[i]=sum[i-1]+a[i];
            else sum[i]=a[i];
            if(a[i]>maxn)maxn=a[i];
        }
        if(x<=0&&maxn>x){printf("1\n");continue;}
        if(x<=0&&maxn<x){printf("-1\n");continue;}
//        cout<<"zz"<<endl;
        int head,tail;
        int ans=n+1;
        a[0]=0;
        int l=0;
        int r=0;
        for(int i=1;i<n;++i)
        {
            while(l<=r&&sum[i]<=sum[a[r]])r--;
            a[++r]=i;
            while(l<r&&(sum[i]-sum[a[l]]>=x))
            {
                ans=min(i-a[l],ans);
                l++;
            }
        }
        if(ans!=n+1)
        {
            printf("%d\n",ans);
        }
        else
        printf("-1\n");
    }
    return 0;
}