SDUT OJ 河床

河床

Time Limit: 3000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

地理学家们经常要对一段河流进行测量分析。他们从上游开始向下游方向等距离地选择了 n（n≤30000）个点测量水位深度。得到一组数据d1，d2，...，dn，回到实验室后数据分析员根据需要对数据进行分析，发掘隐藏在数据背后的规律。最近，乌龙博士发现某种水文现象与河床地势有关，于是他指示分析员要找到一段河流中最大高低起伏差不超过k（k≤100）的最长一段。这看似一个复杂的问题，由于任务紧急，分析员来求助于你，并告诉你博士的所有数据都精确到各位。

输入

输入数据有2行。
第一行是整数n和k，分别表示测量点的个数和博士要求的最大水深差（也就是河床地势差）。
第2行有n个整数，表示从上游开始依次得到的水位深度di（1≤i≤n,0≤di≤32767)。

输出

输出数据只有1行，是整数m，表示最长一段起伏不超过k的河流长度，用测量点个数表示。

示例输入

6 2

5 3 2 2 4 5

示例输出

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int a[30002];

int main()

{

    int n, k; //测量点  最大落差

    int high, low; //当前测量段落的最高点,最低点

    int len, Max; //保存当前长度  保存最终最大长度

    cin>>n>>k;

    int i, j;

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

    {

        cin>>a[i];

    }

    Max=0;

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

    {

        high=a[i];

        low=a[i];

        len=1;

        for(j=i+1; j<n; j++)

        {

            if(a[j]<low)

            {

                low=a[j];

                if((high-low)<=k)

                {

                    len++;

                }

                 if((high-low)>k )

                {

                    if(Max<len)

                      Max=len;

                    break;

                }

            }

            else if(a[j]>high)

            {

                high=a[j];

                if((high-low)<=k)

                {

                    len++;

                }

                else if((high-low)>k )

                {

                    if(len>Max)

                      Max=len;

                    break;

                }

            }

            else

            {

                len++;

            }

         }

         if(len>Max)

           Max=len;

    }

    cout<<Max<<endl;

    return 0;

}

巴特西

SDUT OJ 河床

河床

Time Limit: 3000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

输入

输出

示例输入

示例输出

最新文章

热门文章