主页 / 问题 / 1271291
Accepted
Null
Asked:2022-04-17 17:27:52 +0000 UTC2022-04-17 17:27:52 +0000 UTC

C++ 代码优化/奥林匹克问题

  • 772

有这样一个任务：在此处输入图像描述

我是这样解决的。我们有两个数字：左边框的索引和右边框的索引。首先，我们从左到右将数字相加。如果总和等于给定的，那么我们移动两个边界。如果得到的总和小于给定的总和，那么我们移动右边界。如果结果总和更大，那么我们移动左边框

#include <iostream>
#include "vector"
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int n, k, i, count = 0;
    cin >> n >> k;
    vector<int> autos(n);
    for (auto &h: autos) {
        cin >> h;
    }
    int l = 0, r = 0;
    while (r != n) {
        long long sum = 0;
        for (i = l; i <= r; i++) {
            sum += autos[i];
        }
        if (sum == k) {
            count++;
            l++;
            r++;
        }
        else if (sum < k) {
            r++;
        }
        else if (sum > k) {
            l++;
        }
        sum = 0;
    }
    cout << count;
}

但它没有通过最后一次测试，即 0.081 秒。请建议如何优化此问题。

c++

1 个回答

  1. Best Answer

    移动边界时，不要重新求和。右移 - 加一个数，左移 - 减...

    类型 -

        else if (sum < k) {
        r++;
    }

    写得像

        else if (sum < k) {
        r++;
        sum += autos[r];
    }

    一个

        else if (sum > k) {
        l++;
    }

    如何

        else if (sum > k) {
        sum -= autos[l++];
    }

    sum自然地，在从代码中移动边界之后，去掉求和和归零的循环。取出周期的公告sum。

    • 3

相关问题