HNUST-OJ-主元素

题目描述：

输入：

输入由多组数据组成。
每组数据由二行组成，第一行是整数n(1<=n<=100000), 第二行是n个空格分开的整数，它们的值位于区间[0,1000000000]。
题目保证60%的数据n的值不超过20。 

输出：

每一组输入数据输出一行。如果存在满足条件的x，则输出，否则输出-1。

样例输入：

3
3 2 3
8
0 5 5 3 5 7 5 5
8
0 5 5 3 5 1 5 7

样例输出：

3
5
-1

解题心路历程（I）：
寒假学习了map的一点点皮毛后，就想到了这道题，于是初生牛犊不怕虎的勇气让我决定用map来写这道题，发现时间超限，于是企图通过快读与快写来强行卡时间，然而徒劳。

分享下我用map写的这道题（只过了90%）：

​
//错误示范（时间超限呜呜呜，只有90）
#include<cstdio>
#include<map>
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');
}
int main()
{int n,flag,t;while(scanf("%d",&n)!=EOF){map<int,int>a;flag=-1;for(int i=0; i<n; i++){t=read();a[t]++;if(a[t]>n/2)flag=t;}write(flag);printf("\n");}}​

 解题心路历程（II）：

后来经过提示，发现map会自动排序，暴风哭泣，可能（我也不太确定）是他的排序效率不如快排。

于是不得不用优化版的快排来写，于是最终成果如下：

//结合了某位大佬的做法进行的不自量力的优化
#include<bits/stdc++.h>
using namespace std;
#define swap(a,b) {int tmp=a;a=b;b=tmp;}
void kuai(int a[],int l,int r)
{int mid=a[l+(r-l)/2];int left=l,right=r;while(left<=right){while(a[left]<mid)left++;while(a[right]>mid)right--;if(left<=right){swap(a[left],a[right]);left++;right--;}}if(l<right)kuai(a,l,right);if(left<r)kuai(a,left,r);
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');
}
#define MAX 1000006int a[MAX];
int main()
{int n;while(scanf("%d",&n)!=EOF){for(int i=0; i<n; i++)a[i]=read();kuai(a,0,n-1);int temp=-1,c=0,flag=0;for(int i=0; i<n; i++){if(a[i]!=temp){temp=a[i];c=1;}else c++;if(c>n/2){write(temp);printf("\n");flag=1;break;}}if(!flag){write(-1);printf("\n");}}
}

写在最后：

我还是太弱小了，这个寒假我也不知道自己在通往那群高山的路上行了多少步，希望有所收获。

送大家一句话：

“高山仰止，景行行止。虽不能至，然心向往之。”

最后祝大家新年快乐！！！