【qduoj - 312】寻找唯一的萌妹（卡时）,戴尔手机d43

文件名：【qduoj - 312】寻找唯一的萌妹（卡时）,戴尔手机d43 【qduoj - 312】寻找唯一的萌妹（卡时）

题干：

寻找唯一的萌妹

Description

 

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

Input

 

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

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

Output

 

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

Sample Input 1 

21 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.容器这东西，，，很难说啊