集训第四周（高效算法设计）N题 (二分查找优化题)

原题：poj3061

题意：给你一个数s，再给出一个数组，要求你从中选出m个连续的数，m越小越好，且这m个数之和不小于s

这是一个二分查找优化题，那么区间是什么呢？当然是从1到数组长度了。比如数组长度为10，你先找5，去枚举每一个区间为5的连续的数，发现存在这样的数，那么就可以继续往左找，反之则往右找，直到左右区间重合，即为正确答案，（有可能是右区间小于左区间，所以每次都应该求区间中点值）

#include"iostream"

#include"set"

#include"cstring"

#include"cstdio"

#include"algorithm"

using namespace std;

const int maxn=100000+10;

int a[maxn];

long long sum[maxn];

int n,s;

bool guess(int c)

{

    int temp;

    for(int i=0;i<=n-c;i++)

    {

        temp=sum[c+i]-sum[i];

        if(temp>=s) return true;

    }

    return false;

}

int main()

{

    while(cin>>n>>s)

    {

        sum[0]=0;

        for(int i=0;i<n;i++)

        {

            cin>>a[i];

            sum[i+1]=a[i]+sum[i];

        }

        if(sum[n]<s) cout<<0<<endl;

        else

        {

         int l=0,r=n-1,m,ans=10000;

         while(l<r)

         {

             m=(r+l)/2;

             if(guess(m)) {r=m;}

             else l=m+1;

         }

         m=(r+l)/2;

         cout<<m<<endl;

        }

    }

    return 0;

}

巴特西

集训第四周（高效算法设计）N题 (二分查找优化题)

最新文章

热门文章