2

我试图解决在线法官的问题（ http://www.codechef.com/BTCD2012/problems/DOORS ）。以下是问题的代码。当我提交时，法官给出了运行时错误（其他）。我是否使用了太多内存，如果是这样，请帮助我找到其他方法，因为内存已根据给定的约束使用.

约束如下：

0< t1 <1000000;

0<数量<100000000;

#include<stdio.h>
int a[100000001];
int main()
{

    int  t=3,j,k1,g,k=1,m,n=0,i,t1,num;
    for(i=1;i<10000;i++)
    {
        m=i*i;
        n=n+t;
        for(j=m;j<=n;j++)
        {
            a[j]=k;
        }
        k++;
        t=t+2;
        // printf("a[%d]--> %d\n",n,a[n]);
   }

   scanf("%d",&t1);

   for(k1=0;k1<t1;k1++)
   {
       scanf("%d",&num);
       printf("%d\n",a[num]);
   }
   getch();
   // return 0;
}
4

4 回答 4

1 
int a[100000001];

这行是问题所在，它在静态分配区分配了太多内存！如建议的那样，您可以使用 malloc() 在堆上分配此内存。

更精简的方法是使用一组位[每个位代表一扇门，您只需打开和关闭它们以表示门的打开或关闭状态]。实现起来会有点棘手，但你的程序会更精简（至少 16 次，C int 至少是 2 个字节，16 位）并且更快！

于 2012-08-23T19:48:41.847 回答
1

该行：

int a[100000001];

尝试在堆栈上分配 381.5 MB 的内存。这很可能对于运行时来说太大而无法处理，因此程序将被终止。

你真的需要那么多整数吗？

如果您确实需要那么多内存，请尝试在堆中分配它：

将全局更改为指针：

int *a;

在开始时main()

a = malloc(sizeof(int)*100000001);
if(!a)
{
   printf("Could not allocate contiguous block\n");
   return -1;
}
于 2012-08-23T19:07:22.740 回答
0

嘿，首先是好问题:-)为此“+1”。现在回答您的问题，如果您确定需要这么多内存，那么动态分配内存始终是一个好习惯。尝试. malloc_ variable a你int使用了多少字节？如果unsigned long long您确定不需要任何signed bits.

unsigned int* a ;
a = malloc( sizeof(int) * 100000001 ) ;

上面的答案和评论太有用了。

于 2012-08-28T07:13:43.887 回答
0

试试这个算法..：尝试找出 1 和 n 之间有多少个完美正方形。完美正方形有奇数个倍数，我认为这将是答案。假设 n = 1000，1 之间只有 31 个完美正方形到1000。所以，她离开后打开的门数= 31。

于 2015-07-05T10:53:22.153 回答