boj problem 1330 顺利AC 注意输入或输出数据较多时 scanf printf 比cin cout快非常多~

继续寻找相同Submit: 1095   Accepted:199Time Limit: 2000MS  Memory Limit: 65535K

Description

有 n 个整数，其中有且仅有一个整数出现了 >= n/2.0 次 (n<=5000000)

Input

每组数据第一行是 n，然后接下来一行是 n 个整数。

Output

输出每行格式如A题

Sample Input

9

5 5 5 5 5 1 2 3 4

Sample Output

Case 1: 5

Source

#include<iostream>

using namespace std;

int a[5000001];

int b[5000001];

int main()

{

  int i,n,temp;

  int top;

  int sum=1;

  while(scanf("%d",&n)!=EOF)

  {

 int count=0;

  for(i=0;i<n;i++)

 {

    scanf("%d",&b[i]);

    if(b[0]==b[i])

     count++;

 }

  if(count>=n/2)

  {

     cout<<"Case "<<sum<<": "<<b[0]<<endl;

        cout<<endl;

        sum++;

  }

  else

  {

    top=-1;

      for(i=1;i<n;i++)

   {

    if(top==-1)

    {

       top++;

    a[top]=b[i];

    }

    else

    {

    if(b[i]==a[top])

    {

      top++;

   a[top]=b[i];

    }

    else

    {

       top--;

    }

    }

 }

     cout<<"Case "<<sum<<": "<<a[top]<<endl;

      cout<<endl;

     sum++;

  }

  }

  return 0;

}

思路：利用1329的思路先 由于是>=n/2，所以可以考虑先将第一个数与后面比较，如果是它，直接输出，否则跳过这个，剩下n-1个数就是1329题了~用栈的思路去做，相同入栈，不同出栈，那么一定最后栈顶元素为所求。

学到:scanf与cin在输入数据较多时时间差距十分明显~应该重视~！另外栈的算法应该再熟悉熟悉！