Ignatius and the Princess IV (简单DP,排序)

方法一：直接进行排序，输出第（n+1）/2位置上的数即可。（容易超时，关闭同步后勉强卡过）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int n;
 9 int a[1000005];
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     while(cin>>n)
14     {
15         for(int i=0;i<n;i++)
16         cin>>a[i];
17         sort(a,a+n);
18         cout<<a[(n+1)/2]<<endl;
19     }
20 }

方法二：原 https://www.cnblogs.com/kuangbin/archive/2011/07/30/2122217.html

在一个序列中如果去掉2个不同的元素，
那么原序列中的多元素，在新的序列中还是多元素，
因此我们只要按照序列依次扫描，先把t赋值给result，
增加个计数器，cnt = 1；然后向右扫描，
如果跟result相同，则cnt++，不同，那么cnt --，
这个真是我们从上面那个结论里得出的，一旦cnt == 0了，
那么必定c不是多元素，这个时候把t赋值为result,cnt = 1；，
重复该过程，知道结束，这个时候，result就是多元素，
这个的时间复杂度为n。

这个算法的正确性在于因为我们要输出的Ans的次数是大于等于n/2+1的，也就是说它出现的次数是大于其他所有数出现次数之和的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int n,t,cnt,res;
 9 
10 int main()
11 {
12     ios::sync_with_stdio(false);
13     while(cin>>n)
14     {
15         cnt=0;
16         for(int i=0;i<n;i++)
17         {
18             cin>>t; //复杂度为 n
19             if(cnt==0) //这意味着重新一个数
20             {
21                 res=t; //重新的数 赋给res
22                 cnt++;
23             }
24             else
25             {
26                 if(t==res) cnt++;
27                 else cnt--;
28             }
29         }
30         cout<<res<<endl;
31     }
32 }

然而时间上也是勉强过