zoj_3123二分与分治

分治思想求解，超时了分析了一下T(n)=O(n)+O(logn)*k(k可能渐进为n)

#include <iostream>using namespace std;int sum[100001];int main(){     int repeat,i,m,s,x;     int len,mid,high,low,flag;     cin>>repeat;     while(repeat--)     {        cin>>m>>s;        sum[0]=0;        for(i=1;i<=m;i++)        {            scanf("%d",&x);            sum[i]=sum[i-1]+x;        }        low=1;        high=m;        len=0;        while(low<=high)        {            mid=(low+high)/2;            flag=0;            for(i=mid;i<=m;i++)            {                if(sum[i]-sum[i-mid]>=s)                {                    flag=1;                    len=mid;                    break;                }            }            if(flag)            high=mid-1;            else            low=mid+1;        }        cout<<len<<endl;     }     return 0;}

?