如何减少内存使用？来自 codeforces 的问题

Question

我从 codeforces 解决了这个问题：https://codeforces.com/problemset/problem/1471/B。但是当我上传它时它说超出了内存限制。如何减少内存使用量？我用 C++ 来解决这个问题。问题如下：“你给了一个全新的机器人一个长度为 n 的数组 a 和一个整数 x。机器人所做的如下：它遍历数组的元素，让当前元素为 q。如果 q 可以被 x 整除，则机器人将整数 qx 的 x 个副本添加到数组的末尾，然后移动到下一个元素。请注意，机器人稍后可以处理新添加的元素。否则，如果 q 是不能被 x 整除，机器人关闭。

请在过程结束时确定数组所有值的总和。

这是代码：

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

int main()
{

    vector<int> vec;
    vector<int> ans;
    int temp;

    int t;
    cin >> t;
    int a = 0;
    int n, x;

    for(int i=0; i<t; i++){
            cin >> n >> x;
        while(a<n){
            cin >> temp;
            a++;
            vec.push_back(temp);
        }

        int q = 0;

        while(true){
            if(vec[q]%x == 0){
                for(int copies=0; copies<x; copies++){
                    vec.push_back(vec[q]/x);
                }
            }
            else{
                break;
            }
            q++;
        }

        int sum = 0;
        for(int z: vec){
            sum += z;
        }
        ans.push_back(sum);

        vec.clear();
        a = 0;
    }

    for(int y: ans){
        cout << y << endl;
    }

    return 0;

}

谢谢。

Answer 1

您不需要按照指定的方式构建数组来计算总和

你可能会：

int pow(int x, int n)
{
    int res = 1;

    for (int i = 0; i != n; ++i) {
        res *= x;
    }
    return res;
}

int compute(const std::vector<int>& vec, int x)
{
    int res = 0;
    int i = 0;
    while (true) {
        const auto r = pow(x, i);
        for (auto e : vec) {
            if (e % r != 0) {
                return res;
            }
            res += e;
        }
        ++i;
    }
}

Demo

Answer 2

考虑：

如果您在原始数组中发现一个不可分割的数字，您将在达到您添加的数字之前停止（因此它们不会影响结果）。
如果您将 q/x 添加到数组中，但 q/x 不能被 x 整除，如果您之前没有停止，您将在到达它时停止。（另一方面，如果 q/x 是可被 x 整除，则 q/x 的 x 个副本的总和为 q，因此将它们相加等于添加 q。 )

所以你不需要扩展数组，你只需要对元素求和 - 在一边 - 保留你将要扩展的所有数字的总和，直到找到一个不是倍数的数字x.
然后你要么把它加到数组的总和中，要么不加，这取决于你是否到达数组的末尾。

如何减少内存使用？来自 codeforces 的问题

How to reduce memory usage? Problem from code forces

c++

memory-management