如何减少内存使用?来自代码强制的问题

Question

我从codeforces: https://codeforces.com/problemset/problem/1471/B解决了这个问题。但是当我上传它的时候，它说内存超出限制。如何减少内存使用?我用c++来解决这个问题。问题是这样的:你给了一个长度为n和整数x的数组a给一个全新的机器人。机器人所做的事情如下:它遍历数组中的元素，设当前元素为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;
}
}

演示

Answer 2

考虑:

• 如果你在原始数组中找到一个不可分割的数字，你将在到达你添加的数字之前停止(因此它们不会影响结果)。
• 如果你将q/x添加到数组中，但q/x不能被x整除，如果你之前没有停止，那么当你到达它时，你将停止在那里。(另一方面，如果q/x能被x整除，则q/x的x个副本之和为q，因此将它们相加等于将q相加。)

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