c - 在竞争性算法挑战中获取运行时错误(SPOJ MAJOR)

Question

根据问题，我们必须找出一个元素是否出现超过 n/2 次，然后相应地打印 Yes 或 No。数字可以从 10^-3 到 10^3 不等。

我取了一个数组 count[2005]，然后将 1000 添加到每个输入，使 10^-3 等于 0，即 -1000+1000=0，然后将 -1000 的出现次数存储在 count[0] 中其余元素也一样。因此:

• 下限= -1000+1000=0;
• 上限=1000+1000=2000;

但我仍然遇到内存访问冲突。这是原始问题的链接:http://www.spoj.com/problems/MAJOR/

#include<stdio.h>
int main()
{
    int t,n,a,count[2005],max,check,temp;
    scanf("%d",&t);
    while(t--)
    {
              check=0;
              scanf("%d",&n);
              for(int i=0;i<2005;i++)
                      count[i]=0;
              for(int i=0;i<n;i++)
              {
                      scanf("%d",&a);
                      temp=a+1000;
                      count[temp]++;
                      if(count[temp]>(n/2))
                      {
                                         check=1;
                                         max=temp-1000;
                                         break;
                      } 
              }
              if(check==1)
                          printf("YES %d\n",max);
              else
                  printf("NO\n");
                        
    }
    return 0;
}

Answer 1

您的代码的问题是您没有完全读取输入 - SPOJ 要求您的程序应该完全读取输入，而不是在中间中断。

您的问题的解决方案:只需取一个大小为 (10^6+1) 的 arr 并首先读取所有输入，然后应用算法。 请记住这一点，如果您在读取输入时也中断了，它将始终是 SIGSEGV。因此，请始终完整阅读每个编程网站上的输入内容。

这是您修改后的代码，可以获取 AC 了:

#include<stdio.h>
int arr[1000002]; // Array of Size (10^6+2)
int main()
{
    int t,n,a,count[2005],max,check,temp,i;
    scanf("%d",&t);
    while(t--)
    {
              check=0;
              scanf("%d",&n);
              for(int i=0;i<2005;i++)
                      count[i]=0;

              for(i=0;i<n;i++)
                       scanf("%d",&arr[i]);  // READING INPUT FULLY IN AN ARRAY
              
               for(i=0;i<n;i++)
              {
                      a=arr[i]; // Now, a=arr[i] and previous algorithm applies now 
                      temp=a+1000;
                      count[temp]++;
                      if(count[temp]>(n/2))
                      {
                                         check=1;
                                         max=temp-1000;
                                         break;
                      } 
              }
              if(check==1)
                          printf("YES %d\n",max);
              else
                  printf("NO\n");
 
    }
    return 0;
}