题干：

寻找唯一的萌妹

Description

 

又到了一年一度ACMer暑期留校集训的日子了，目前一共有2n+1个小萌新报名参加暑期集训，其中2n个是帅哥，只有1个萌妹子，这是多么的悲催！由于暑期训练强度大，坚持下来可不是一件容易的事情，DHG学长想到了一个巧妙的方法，两个人组成一队，两人互相鼓励，互相监督，直到集训顺利完成。然而，只有具有相同抗压能力的两位同学才能组在一起，并且这个唯一的萌妹子比较高傲不愿意和现有的2n个帅哥组队，只想和下一个报名的同学组队。作为仍未报名的你，想和这传说中的萌妹子组队，要求你输出萌妹子的抗压能力值。

Input

 

第一行一个n(n<=1000000)

第二行2n+1个数,表示每个小萌新的抗压能力值xi(-99999999<xi<99999999)。

Output

 

只输出一个数字，表示萌妹的抗压能力值。

Sample Input 1 

2
1 2 2 1 3

Sample Output 1

3

Sample Input 2 

1
-2 -2 1

Sample Output 2

1

Hint

题目保证：有正确答案；

 

解题报告：

      这是集训队纳新的一道题目，比赛时是用map做的。超时了。

     其实用map也是可以的但是要用迭代器遍历或者mp[ a[i] ]这样遍历，而不能从-99999999~~+99999999这样遍历，这不是作死吗。

 

TLE代码：（1040ms）

#include<iostream>
#include<map>
#include<list>
#include<algorithm>
using namespace std;
list<int> lili;
bool cmp(const int & a,const int & b ) {
	return a<b;
}
map<int,int> mp;
int main()
{
	int n;
	int tmp;
	scanf("%d",&n);
	n=n*2+1;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&tmp);
		if(mp[tmp]==1) {
			list<int> :: iterator it;
			for(it=lili.begin();it!=lili.end(); it++ ) {
				if(*it==tmp) break;
			}
			lili.erase(it);
			mp[tmp]=0;
		}
		else {
			mp[tmp]=1;
			lili.push_back(tmp);
		}
	}
	cout << lili.front() << endl;
	return 0; 
}

TLE代码2：（1272ms）

#include<iostream>
#include<map>
#include<list>
#include<algorithm>
using namespace std;
list<int> lili;
bool cmp(const int & a,const int & b ) {
	return a<b;
}
map<int,int> mp;
int main()
{
	int n;
	int tmp;
	scanf("%d",&n);
	n=n*2+1;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&tmp);
		if(mp[tmp]==1) {
			mp.erase(tmp);
		}
		else {
			mp[tmp]=1;
		}
	}
	map<int,int> :: iterator it;
	for(it=mp.begin();it!=mp.end();it++) {
		printf("%d\n",*it);
	}
	return 0; 
}

wa代码：（1376ms）

#include<iostream>
#include<map>
using namespace std;
//int a[100000000];
map<int,int> mp;
int main()
{
	int n;
	int tmp;
	scanf("%d",&n);
	n=n*2+1;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&tmp);
		mp[tmp]++;
	}
	for(int i = 1; i<=n; i++) {
		if(mp[i]&1) {
			printf("%d\n",i);
			break;
		}
	}
	return 0 ;
}
//2
//1 2 2 1 3

ac代码：

#include<iostream>
#include<algorithm>

using namespace std;
int a[2000005];

int main()
{
	int n;
	scanf("%d",&n);
	n=n*2+1;
	for(int i = 1; i<=n; i++) {
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1); 
	int cnt=1;
	int tmp=a[1];
	for(int i = 2; i<=n; i++) {
		if(tmp==a[i]) {
			cnt++;
		}
		else {
			if(cnt&1) {
				printf("%d",a[i-1]);
				return 0 ;
			}
			else {
				tmp=a[i];
				cnt=1;
			}
		}
	}
	printf("%d",a[n]);
//if(a[i]==a[i-1]) {
//			cnt++;
//			continue;
//		}
//		if( (cnt&1) ) {
//			printf("%d",a[i]); 
//			return 0;
//		}
//		cnt=1;
//	printf("$dddd");
	return 0 ;
 }

总结：

   1.首先注意数组别开小  开一个1e6肯定上来就玩完了直接RE告辞。得开2e6啊这题！

   2.容器这东西，，，很难说啊