i题很多人提交并且AC的那个代码其实是错的

最近解i题的时候发现之前过的很多人提交的代码都大同小异,核心代码是这样的:
memset(mod, 0, sizeof(mod));
for (int i = 0; i < n; ++i) {
scanf("%d", &num);
sum[i + 1] = (ll)sum[i] + num;
}
ll  maxsum = 0;
int maxlen = 0, res;
for (int i = 1; i <= n; ++i) {
res = sum[i] % m;
if (mod[res]) {
maxlen = max(maxlen, i - mod[res]);
maxsum = max(maxsum, sum[i] - sum[mod[res]]);
}
else
mod[res] = i;
}
printf("%lld %d\n", maxsum, maxlen);
这个代码还都AC了,所以才有这么多人借鉴这份代码吧(我也是借鉴的这份代码(手动流汗)),但实际上这个代码是有问题的,只要当前缀和数组sum[i]%m就等于0的时候就有可出现错误,比如以下一个简单的测试数据:
5 5
1 2 1 10 6
运行这份代码得到的结果是10 1
但很明显,我们心算就能得到结果是 20 5。
所以这份代码要做一个小的改动:
memset(mod, -1, sizeof(mod));//初始化不能为0,可以设为-1(也可以是其他数)
for (int i = 0; i <= n; ++i) //循环要从0开始,这样才能处理sum[i]%m==0的情况
if (mod[res]!=-1)
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-24 12:26
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
07-02 22:46
门头沟学院 Java
码农索隆:hr:“管你投没投,先挂了再说”
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务