玩数字编程挑战(子数组的平均值)

Question

我正试图解决Hackerearth中的数字游戏问题。我已经通过了测试用例，但是，我总是被超过时间限制。有人能帮我提高它的性能以通过时间限制吗？

这是我的代码-

#include <iostream>
using namespace std;
int main()
{
int n, q, i, l, r, j, sum;
cin >> n >> q;
int *arr = new int[n];
for (i = 0; i < n; i++)
{
cin >> arr[i];
}
for (i = 0; i < q; i++)
{
sum = 0;
cin >> l >> r;
for (j = l - 1; j <= r - 1; j++)
{
sum += arr[j];
}
cout << sum / (r - l + 1) << endl;
}
delete[] arr;
}

Answer 1

您必须移除内部循环。存储累积和，而不是将元素存储在数组中。

E。g.元素为1、2、2、1、4。您必须存储1、(1+2=(3、(1+2+2=(5、(1+2+2+1=(6、(1++2+2+1+4=(10。然后可以使用last_element-first_element计算子数组的和。

E。g.对于起始索引2和结束索引=5，得到2+2+1+4=10-1。你不需要内环。