整型数组能定义为多大的？

今天练习CCF202006-2时遇到一个问题，我需要定义10^9+1那么大的整型数组，但程序运行时老是自动退出，我怀疑是因为10^9太大了，将其改为10^5后果然可正常运行了。我的原始代码如下：

#include<iostream>
#include<math.h>
#include<stdlib.h> 
#include<memory.h>
using namespace std;

const int MAX=1000000000;

int main()
{
    int u[MAX+1], v[MAX+1];
    memset(u, 0, sizeof(u));
    memset(v, 0, sizeof(v));
    
    int n, a, b;
    int index, value;
    int sum=0;
    
    cin>>n>>a>>b;
    while(a--)
    {
        cin>>index>>value;
        u[index]=value;
    }
    while(b--)
    {
        cin>>index>>value;
        v[index]=value;
    }
    
    for(int i=1; i<=MAX+1; i++)
    {
        sum+=u[i]*v[i]; 
    }
    cout<<sum<<endl;
    return 0;
}

经过查询资料，发现原因如下：

我的数组u[MAX+1]和v[MAX+1]声明在了函数内部，属于局部变量，存放在了栈上。

栈的默认内存空间为1M左右。

让我们来算算我的数组占用了多少空间：

10^9*4B =（10^9*4/2^20）MB ≈ （4*1000*1000*1000/1024/1024）MB ≈ 4000MB远大于1MB

所以会导致内存溢出。

怎么解决呢？可以将数组声明在全局存储区或堆上。

修改后的程序如下：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<stdlib.h> 
 4 #include<memory.h>
 5 using namespace std;
 6 
 7 const int MAX=1000000000;
 8 int u[MAX+1];
 9 int v[MAX+1];
10 
11 int main()
12 {
13     
14     memset(u, 0, sizeof(u));
15     memset(v, 0, sizeof(v));
16     
17     int n, a, b;
18     int index, value;
19     int sum=0;
20     
21     cin>>n>>a>>b;
22     while(a--)
23     {
24         cin>>index>>value;
25         u[index]=value;
26     }
27     while(b--)
28     {
29         cin>>index>>value;
30         v[index]=value;
31     }
32     
33     for(int i=1; i<=MAX+1; i++)
34     {
35         sum+=u[i]*v[i]; 
36     }
37     cout<<sum<<endl;
38     return 0;
39 }

可是这样还是不行，嘤嘤嘤，大概是因为10^9真的太大了吧。

改成放在堆上，代码如下：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<stdlib.h> 
 4 #include<memory.h>
 5 using namespace std;
 6 
 7 const int MAX=1000000000;
 8 
 9 int main()
10 {
11     int *u, *v;
12     u=new int[MAX+1];
13     v=new int[MAX+1];
14     memset(u, 0, sizeof(u));
15     memset(v, 0, sizeof(v));
16     
17     int n, a, b;
18     int index, value;
19     int sum=0;
20     
21     cin>>n>>a>>b;
22     while(a--)
23     {
24         cin>>index>>value;
25         u[index]=value;
26     }
27     while(b--)
28     {
29         cin>>index>>value;
30         v[index]=value;
31     }
32     
33     for(int i=1; i<=MAX+1; i++)
34     {
35         sum+=u[i]*v[i]; 
36     }
37     cout<<sum<<endl;
38     delete[] u;
39     delete[] v;
40     return 0;
41 }

注意new了要delete！

这样内存不溢出了，可是运算超~极~慢~，算法不行。

最终修改如下：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<stdlib.h> 
 4 #include<memory.h>
 5 using namespace std;
 6 
 7 const int MAX=1000000000;
 8 
 9 int main()
10 {
11     int *u;
12     u=new int[MAX+1];
13     memset(u, 0, sizeof(u));
14     
15     int n, a, b;
16     int index, value;
17     int sum=0;
18     
19     cin>>n>>a>>b;
20     while(a--)
21     {
22         cin>>index>>value;
23         u[index]=value;
24     }
25     while(b--)
26     {
27         cin>>index>>value;
28         sum+=u[index]*value;
29     }
30     
31     cout<<sum<<endl;
32     delete[] u;
33     return 0;
34 }

原以为会AC的，可是我运行错误了，呜呜呜

修改如下：

 1 #include<iostream>
 2 #include<math.h>
 3 #include<stdlib.h> 
 4 #include<memory.h>
 5 using namespace std;
 6 
 7 const int MAX=1000000000;
 8 
 9 int main()
10 {
11     int *u;
12     int n, a, b;
13     int index, value;
14     int sum=0;
15     
16     cin>>n>>a>>b;
17     u=new int[n+1];
18     memset(u, 0, sizeof(u));
19     while(a--)
20     {
21         cin>>index>>value;
22         u[index]=value;
23     }
24     while(b--)
25     {
26         cin>>index>>value;
27         sum+=u[index]*value;
28     }
29     
30     cout<<sum<<endl;
31     delete[] u;
32     return 0;
33 }

修改成这样只得60，我要哭了

 1 #include<iostream>
 2 #include<stdlib.h> 
 3 #include<memory.h>
 4 using namespace std;
 5 
 6 long long sum=0;
 7 int main()
 8 {
 9     long long *u;
10     int n, a, b;
11     int index, value;
12     
13     cin>>n>>a>>b;
14     u=new long long[n+1];
15     memset(u, 0, sizeof(u));
16     while(a--)
17     {
18         cin>>index>>value;
19         u[index]=value;
20     }
21     while(b--)
22     {
23         cin>>index>>value;
24         sum+=(long long)u[index]*(long long)value;
25     }
26     
27     cout<<sum<<endl;
28     delete[] u;
29     return 0;
30 }

还是60

放弃了放弃了，告辞吧您嘞