求子数组中任意两数之和能整除k的最大元素个数 - 编程论坛

#2

diycai2021-11-17 12:59

程序代码：

#include <stdio.h>
int goodSeries(int *a, int n, int s)
{
    int i, len=0, b=-1, t=-1;
    for (i=0; i<n-1; i++)
    {
        if (((a[i]+a[i+1])%s) == 0)
        {
            b = 2;
            break;
        }
    }
    if (s&1)
    {
        for (i=0; i<n; i++)
        {
            if ((a[i]%s) == 0)
            {
                len++;
            }
            else
            {
                if (len > b)
                {
                    b = len;
                }
                len = 0;
            }
        }
        if (len > b)
        {
            b = len;
        }
    }
    else
    {
        for (i=0; i<n; i++)
        {
            if ((a[i]%s) == t)
            {
                len++;
            }
            else
            {
                if (len > b)
                {
                    b = len;
                }
                t = -1;
                len = 0;

                if ((a[i]%s) == 0)
                {
                    t = 0;
                    len++;
                }
                else if ((a[i]%s) == (s>>1))
                {
                    t = s>>1;
                    len++;
                }
            }
        }
        if (len > b)
        {
            b = len;
        }
    }
    return b;
}

void main()
{
    int a[100000];
    int n, k, i, b;
    char tmp;
    scanf("%d%d", &n, &k);

    for (i=0; i<n; )
    {
        if (scanf("%d", a+i) == 0)
        {
            scanf("%c", &tmp);
            continue;
        }
        i++;
    }
    b = goodSeries(a, n, k);
    printf("%d\n", b);
}

#3

lin51616782021-11-17 17:05

回复 2楼 diycai

    for (i=0; i<n-1; i++)
    {
        if (((a[i]+a[i+1])%s) == 0)
        {
            b = 2;
            break;
        }
    }

这一段的思路应该是错的
你准备挑选出两个和能整除s
作为其他情况不满足的最后可选
但是只检查连续不合理呀
比如
序列
1 5 6 100
s是7
结果序列应该是 [1 6] 或者[5 100] 不连续的
那你的这个循环就错过了正确选项了

#4

diycai2021-11-17 18:26

回复 3楼 lin5161678

你再看一下题目，是任意两个都满足，而不是任选两个满足即可。

#5

lin51616782021-11-18 08:56

回复 4楼 diycai

我说的是对于数列 [1, 5, 6, 100] s == 7的情况
选出子数列 [1, 6] 满足任意两个加起来整除7的要求

我看明白了你以为子数组是连续的?
不是的从数组里面删除任意多的元素得到的都是这个数组的子数组

#6

rjsp2021-11-18 09:28

这题目连个示例都不肯给，纯属浪费时间。

@diycai
按照 lin5161678 所言，我输入 4 7 1 5 6 100，你的程序输出 0，但正确的结果应该是 2 呀！

我简单思考了一下，
假设 K型好数列有三个数，那么这三个数必然是 { x，a*k-x，(b+2*x/k)*k-x }，
也就是 2x 可以被 k 整除，
也就是这些数要么全是k的倍数，要么全是 k的倍数 + k的半数
以上是三个及三个以上的情况。

程序代码：

#include <stdio.h>

int main( void )
{
    int a[] = { 1, 5, 6, 100 };
    int k = 7;

    size_t maxlen = 0;
    const size_t n = sizeof(a)/sizeof(*a);
    for( size_t i=0; i!=n; ++i ) // 统计k的倍数
        maxlen += a[i]%k == 0;
    if( k%2 == 0 ) // 统计k的 ?.5倍的数
    {
        size_t half = 0;
        for( size_t i=0; i!=n; ++i )
            half += a[i]%k == k/2;
        if( maxlen < half )
            maxlen = half;
    }
    if( maxlen < 2 ) // 考虑两个的情况
    {
        for( size_t i=0; maxlen!=2 && i!=n; ++i )
            for( size_t j=i+1; maxlen!=2 && j!=n; ++j )
                if( (a[i]+a[j])%k == 0 )
                    maxlen = 2;
    }

    printf( "%zu\n", maxlen ); // 我没有按照题目要求在小于2时输出-1，因为我觉得这要求无聊
}

#7

diycai2021-11-18 09:57

回复 5楼 lin5161678

子数组

子数组的定义：一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素)

#8

lin51616782021-11-18 14:39

以下是引用diycai在2021-11-18 09:57:21的发言：

子数组

子数组的定义：一个或连续多个数组中的元素组成一个子数组(子数组最少包含一个元素)

看吧你果然对子数组子序列的理解出错了
子序列不要求连续的可能还会要求顺序一致(不过这个题目顺序无关不管是否一致结果不变)
你可以找找其他带子序列的题目对比一下比如最长递增子序列

你说的连续的子序列一般会描述为子串比如最长回文子串

比如
https://blog.
这文章刚刚好是在讲解最长回文子串 & 最长回文子序列
你可以比较一下其中的区别

#9

diycai2021-11-18 14:54

回复 8楼 lin5161678

不是我理解的，是标准定义的。题目要求的是子数组。

只有本站会员才能查看附件，请登录

#10

diycai2021-11-18 15:14

回复 8楼 lin5161678

再来看数组的定义：
数组是逻辑上连续的一系列元素。

那么子数组也要符合这个定义。

在逻辑学上，叫做数组蕴含子数组。

#11

lin51616782021-11-18 17:14

以下是引用diycai在2021-11-18 14:54:12的发言：

不是我理解的，是标准定义的。题目要求的是子数组。

你所说的标准是在哪里找到的呢
我从来没见过子序列子数组这些内容的标准描述