Sicily 1137. 河床

1137. 河床

Constraints

Time Limit: 10 secs, Memory Limit: 32 MB

Description

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

Input

输入文件有两行：

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

Output

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

Sample Input

6 2
5 3 2 2 4 5

Sample Output

4

提示，就是从第二个测量点到第五个测量点之间的那段：5 3 2 2 4 5。他们起伏最大是4-2=2。

Problem Source

ZSUACM Team Member

0.02s：

#include <stdio.h>
#include <math.h>
int a[30001];

int findmax(int i, int j) {
    int max = a[i];
    for (int k = i; k <= j; k++)
        if (max < a[k])
            max = a[k];
    return max;
}

int findmin(int i, int j) {
    int min = a[i];
    for (int k = i; k <= j; k++)
        if (min > a[k])
            min = a[k];
    return min;
}

int main() {
    int n, cha, i, j, b[30001], max, counter, min, max1;
    scanf("%d %d", &n, &cha);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (i = 0; i < n; i++) {
        max = min = a[i];
        for (j = i + 1, counter = 1; j < n; j++) {
            min = findmin(i, j);
            max = findmax(i, j);
            if (max - min > cha)
                break;
            counter++;
        }
        b[i] = counter;
    }
    max1 = b[0];
    for (i = 1; i < n; i++)
        if (b[i] > max1)
            max1 = b[i];
    printf("%d\n", max1);
    return 0;
}    

0.01s：

#include <stdio.h>
int main() {
    int a[30001], max_l, max_differ, i, j, max_pos, min_pos, may_max, max, min;
    scanf("%d%d", &max_l, &max_differ);
    for (i = 0; i < max_l; i++) {
        scanf("%d", &a[i]);
    }
    for (i = 0, may_max = 1; i < max_l; ) {
        
        if (max_l - i <= may_max)
            break;
        
        for (j = i + 1, max = min = a[i], max_pos = min_pos = i; j < max_l; j++) {
            if (a[j] > max) {
                max = a[j];
                max_pos = j;
            } else if (a[j] < min) {
                min = a[j];
                min_pos = j;
            }
            if (max - min <= max_differ) {
                if (j - i + 1 > may_max) {
                    may_max = j - i + 1;
                }
            } else {
                i = (min_pos < max_pos ? min_pos : max_pos) + 1;//直接跳到最前面的最大或最小值的位置后一个位置，因为在此之前都包含了最大最小值，都是不行的
                break;
            }
        }
    }
    printf("%d\n", may_max);
    return 0;
}