c - 该程序通过了我大学的评分器(所有测试用例)，但我的电脑出现段错误

Question

该程序使用限制 (low,up) 在 int 数组 (Kseek) 中进行二分搜索。请忽略一些看起来很奇怪的说明，我还没有完成所有必须做的事情。

奇怪的是，我的代码在我的大学评分器中运行完美，但在我的电脑中出现大型测试用例的段错误。我无法理解错误在哪里，对于具有 N>4000 个元素的输入，它会崩溃。

我不使用任何指针或任何内存分配，我认为 scanf 可能会出现段错误并尝试更改一些属性，但它仍然崩溃。

是否有可能gcc在编译期间有“内存分配边界”，然后当我尝试运行程序时它无法分配我需要的内存大小？

如果您有时间请检查我的代码，可能存在我无法发现的错误。

提前致谢!

   #include <stdio.h>  


int main()  
{  
    int N, K, up, low, pos, flag=1 ;  
    scanf("%d %d\n", &N, &K);  
    int s[N], f[N], i=0;  
    while( scanf("%d %d\n", &s[i], &f[i]) != EOF)  { i++; }  
    i=0;  
    up=f[0];  
    low=s[0];  
    while(i < N )  
        {  
        if ( f[i] > up) up=f[i];  
        if ( s[i] < low) low=s[i];  
        i++;  
    }  
    int Kseek[up];  
    i=0;  
    while( flag )  
    {  
        pos = ( low + up ) / 2;  
        i=0;  
        Kseek[pos]=0;  
        while ( i < N)  
        {  
            if ( pos >=  f[i] )  
                        {  
                                Kseek[pos]=f[i]-s[i]+1+Kseek[pos];  
                        }  
                        else if ( pos >= s[i] && pos <f[i])  
                        {  
                                Kseek[pos]=pos-s[i]+1+Kseek[pos];  
                        }  
                        i++;  
                }  
        if ( Kseek[pos] == K ) flag=0;  
        else if ( Kseek[pos] > K )  
        {  
            i=0;  
            Kseek[pos-1]=0;  
            while ( i < N)  
                        {  
                             if ( (pos-1) >=  f[i] )  
                             {  
                                     Kseek[pos-1]=f[i]-s[i]+1+Kseek[pos-1];  
                             }  
                             else if ( (pos-1) >= s[i] && (pos-1) <f[i])  
                             {  
                                     Kseek[pos-1]=(pos-1)-s[i]+1+Kseek[pos-1];  
                             }  
                             i++;  
                    }  
            if ( Kseek[pos] > K && Kseek[pos-1] < K) flag=0;  
            else if ( Kseek[pos-1] == K ) {  pos-=1; flag=0; }  
            up = pos - 1;   

        }  
        else if ( Kseek[pos] < K)  
        {  
            i=0;  
            Kseek[pos+1]=0;       
            while ( i < N)  
                        {  
                             if ( (pos+1) >=  f[i] )  
                             {  
                                     Kseek[pos+1]=f[i]-s[i]+1+Kseek[pos+1];  
                             }  
                             else if ( (pos+1) >= s[i] && (pos+1) <f[i])  
                             {  
                                     Kseek[pos+1]=(pos+1)-s[i]+1+Kseek[pos+1];  
                             }  
                             i++;  
                }  
                if ( (Kseek[pos+1] > K && Kseek[pos] < K) || Kseek[pos+1] == K) {  flag=0; pos+=1; }  
            low = pos + 1;  



                }  


    }         
    printf("%d\n", pos);  
    return 0;  

}    

输入文件看起来总是这样。条目数量从 10 到 50000 不等:

    200 50536
    369 732
    595 644
    460 500
    548 975
    270 546
    662 766
    358 767
    719 929
    284 354
    411 949
    169 210
    488 679
    103 462
    180 188
    364 487
    407 477
    234 586
    23 775
    504 698
    79 906
    ......
    ...

第一行始终是 K 和 N，接下来的 N 行是 s[i]、f[i]。

Answer 1

我认为这是一件非常微不足道的事情。使用 GCC 和默认选项编译代码，然后使用 VC 中的 dumpbin 转储 a.exe 信息:

OPTIONAL HEADER VALUES
             10B magic # (PE32)
            2.23 linker version
            2E00 size of code
            4800 size of initialized data
             200 size of uninitialized data
            1570 entry point (00401570)
            1000 base of code
            4000 base of data
          400000 image base (00400000 to 0041BFFF)
            1000 section alignment
             200 file alignment
            4.00 operating system version
            1.00 image version
            4.00 subsystem version
               0 Win32 version
           1C000 size of image
             400 size of headers
           183F2 checksum
               3 subsystem (Windows CUI)
               0 DLL characteristics
>>        200000 size of stack reserve
>>          1000 size of stack commit
          100000 size of heap reserve
            1000 size of heap commit
               0 loader flags
              10 number of directories

这两个东西是不是太小而无法将 s[] 和 f[] 保留在堆栈上？我建议重新编译: gcc -Wl,--stack, ... Increase Stack Size on Windows (GCC)

我还制作了另一个源内 mod:只需将 VLA 更改为固定大小的(足够大) - 不再出现堆栈溢出:

         1000000 size of stack reserve
            1000 size of stack commit

好的，我对这个问题的最终更新是确保传入足够的输入数据。当 EOF 在所有 f[] 和 s[] 值被扫描之前出现时，您可以简单地忽略这种情况。我的建议是将 while() 改为 for()。

int i=0;  
for (i=0; i<N; i++) 
    scanf("%d %d\n", &s[i], &f[i]);