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在輸入資料較多時時間差距十分明顯~應該重視~！另外棧的算法應該再熟悉熟悉！