zoj_31232分与分治

zoj_3123二分与分治

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

#include<iostream>
#include<stdio.h>
using namespace std;
int cases,total,sum;
const int maxm=100000;
int array[maxm];
int enumFind(int*array,int start,int end)
{
	int mid=(start+end)/2;
	for(int i=mid;i>=start;i--)
	{
		for(int j=mid+1;j<=end;j++)
		{
			int a=0;
			for(int k=i;k<=j;k++)
			{
				a+=array[k];
			}
			if(a>=sum)
			{
				return j-i+1;
			}	
		}
	}
	return 0;
}
int binaryFind(int* array,int start,int end)
{
	if(start==end)
	{
		if(array[start]>=sum)
			return 1;
		else
			return 0;
	}
	else
	{
		int mid=(start+end)/2;
		int fore=binaryFind(array,start,mid);
		int behind=binaryFind(array,mid+1,end);
		int enu=0;
		int min=0;
		if(fore>0)
		min=fore;
		if(behind>0&&min==0)
		min=behind;
		if(behind>0&&min>0)
		{
			if(behind<min)
			min=behind;	
		}
		if(fore==0&&behind==0)
		{
			enu=enumFind(array,start,end);
		}
		else
		{
			if(min>2)
			enu=enumFind(array,mid-min+3,mid+min-2);
		}
		if(min==0)
		min=enu;
		else
		{
			if(enu>0&&enu<min)
			min=enu;
		}
		return min;
	}
}
int main()
{
	cin>>cases;
	while(cases--)
	{
		cin>>total>>sum;
		for(int i=0;i<total;i++)
		{
			//cin>>array[i];
			scanf("%d",array+i);	
		}
		cout<<binaryFind(array,0,total-1)<<endl;
	}
	return 0;
}

 网上找了个二分法，以搜索的连续字符长度为变量二分，AC了

#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;
}