鱼C论坛

 找回密码
 立即注册
查看: 1134|回复: 2

[已解决]为什么暴力能满分,前缀和就不能满分呢?

[复制链接]
发表于 2023-6-28 18:44:36 | 显示全部楼层 |阅读模式
30鱼币
这边我在一个小oj上刷题
然后就找到了一到求一个数组中最大连续部分和的题目
心想,好一个简单的练习前缀和的题目!由于前缀和的解法与暴力差不多,所以我就先写的暴力,然后就直接ac了
接下来我尝试用前缀和做,代码是这样的(注释部分代表暴力),结果呢,70分
#include <iostream>
using namespace std;
int a[1000], b[1000];
int main(){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++){
                cin >> a[i];
                b[i] = b[i - 1] + a[i];
        }
        /*
        int max = -999;
        for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n - i + 1; j++){
                        int sum = 0;
                        for (int k = j; k <= j + i; k++){
                                sum += a[k];
                        }
                        if (sum > max){
                                max = sum;
                        }
                }
        }
        */
        int max = -999;
        for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n - i + 1; j++){
                        int sum = b[j + i] - b[j - 1];
                        if (sum > max){
                                max = sum;
                        }
                }
        }
        cout << max;
        return 0;
}
这边循环的话i是长度,j是起始下标,k是为了求和
这个我觉得没有问题啊,是我的代码哪里有问题还是oj有问题啊
最佳答案
2023-6-28 18:44:37
根据你提供的代码,前缀和部分的实现看起来是正确的。然而,有一个细微的错误可能导致得到错误的结果。

在第二个循环中,内层循环的起始下标应该为j,终止下标应该为j+i-1,而不是j+i。这是因为数组的下标从1开始,而不是0。

修改后的代码如下:
int max = -999;
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n - i + 1; j++){
        int sum = b[j + i - 1] - b[j - 1];
        if (sum > max){
            max = sum;
        }
    }
}
cout << max;
请尝试修改代码并重新提交,看是否能够得到正确的结果。如果问题仍然存在,请检查其他部分代码是否有问题,或者考虑联系OJ平台的管理员以获取更多帮助。
若有疑问,请继续提问!

最佳答案

查看完整内容

根据你提供的代码,前缀和部分的实现看起来是正确的。然而,有一个细微的错误可能导致得到错误的结果。 在第二个循环中,内层循环的起始下标应该为j,终止下标应该为j+i-1,而不是j+i。这是因为数组的下标从1开始,而不是0。 修改后的代码如下: 请尝试修改代码并重新提交,看是否能够得到正确的结果。如果问题仍然存在,请检查其他部分代码是否有问题,或者考虑联系OJ平台的管理员以获取更多帮助。 若有疑问,请继续提 ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-6-28 18:44:37 | 显示全部楼层    本楼为最佳答案   
根据你提供的代码,前缀和部分的实现看起来是正确的。然而,有一个细微的错误可能导致得到错误的结果。

在第二个循环中,内层循环的起始下标应该为j,终止下标应该为j+i-1,而不是j+i。这是因为数组的下标从1开始,而不是0。

修改后的代码如下:
int max = -999;
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n - i + 1; j++){
        int sum = b[j + i - 1] - b[j - 1];
        if (sum > max){
            max = sum;
        }
    }
}
cout << max;
请尝试修改代码并重新提交,看是否能够得到正确的结果。如果问题仍然存在,请检查其他部分代码是否有问题,或者考虑联系OJ平台的管理员以获取更多帮助。
若有疑问,请继续提问!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2023-6-28 19:26:10 | 显示全部楼层
高山 发表于 2023-6-28 19:20
根据你提供的代码,前缀和部分的实现看起来是正确的。然而,有一个细微的错误可能导致得到错误的结果。

...

懂了,但还是不知道为啥暴力可以过
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 07:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表