有一道oj题，求大佬解答 - 编程论坛

#2

萌新小白太难2020-06-21 22:43

时间有点紧急，希望大佬能帮助下

#3

牧人马2020-06-22 01:02

最简单的用直接法就行，乱序的话先给数组排序。先通过循环从2开始，寻找2~2+6范围内几棵树用max记录，在从3~9记录范围内几棵树，如果树的数量大于max，就更新max，这样一直寻找到（21-6）~21，即（最远距离-L）~（最远距离），最后的max就是所求的数量，注意变量别越界

#4

rjsp2020-06-22 08:33

题目没交代 N 的取值范围吗？
如果题目交代了，你却没肯贴出来，那真是……

#5

萌新小白太难2020-06-22 09:20

回复 4楼 rjsp

确实没给N的范围

#6

萌新小白太难2020-06-22 09:21

回复 3楼牧人马

感谢大佬

[此贴子已经被作者于2020-6-22 09:26编辑过]

#7

rjsp2020-06-22 09:27

以下是引用萌新小白太难在2020-6-22 09:20:33的发言：

确实没给N的范围

那你在main函数中用malloc动态分配内存吧

程序代码：

#include <stdio.h>

unsigned foo( unsigned n, const unsigned pos[], unsigned l )
{
    unsigned max_count = 0;
    for( unsigned i=0, first=0; i!=n; ++i )
    {
        for( ; pos[i]-pos[first]>l; ++first );
        max_count = max_count<(i+1-first) ? (i+1-first) : max_count;
    }
    return max_count;
}

int main( void )
{
    unsigned pos[] = { 2, 4, 9, 10, 11, 13, 14, 19, 20, 21 };
    unsigned count = foo( sizeof(pos)/sizeof(*pos), pos, 6u );
    printf( "%u\n", count );
}

#8

lin51616782020-06-22 10:01

长度没有超过范围右边加
长度超过范围左边减
我不清楚这个做法术语叫啥
我习惯描述为爬虫蠕动前进

程序代码：

int foo( int n, const int pos[], int l )
{
    int res = 0;
    int count = 0;
    for( int i=0, j=0; ;  )
    {
        if(count > l)
            count = pos[i] - pos[++j];
        if(count <= l)
        {
            if(i + 1 == n)
                break;
            count = pos[++i] - pos[j];
        }

        if(res < i-j && count <= l)
             res = i-j;
    }
    return res + 1;
}

[此贴子已经被作者于2020-6-22 10:10编辑过]