洛谷P 2397 yyy loves Maths VI(mode)&校積分試合(五)F.Alexの昼食

テーマの背景
前回redbagが足し算でyyyさんをいじめた後、yyyはとても怒った.彼はredbagにも打ったが、この問題は自分もできないことに驚いたので、あなたを探すしかなかった.
タイトルの説明
[h 1]udp 2:第1題は言語的な問題のため、試合終了後にすべてのc/c++のプログラムのメモリを2.2 mbに調整して再測定する.[/h1]
彼はredbagに衆数を探させた
彼はわざわざ、この衆数の出現回数が半分を超えたと述べた.
全部でn個の数で、しかも保証されています.
n<=2000000
そして各数<2^31-1
入力フォーマット
1行目の整数n
2行目n個の整数
出力フォーマット
一行、この衆数
入出力サンプル
入力#1コピー

5
2 3 3 3 3

出力#1コピー

3

説明/ヒント
時間制限1 s
スペース制限3.5 M(3.5 Mを見間違えていません)
誰かが水を渡りたいと思っていますが、この空間は足りないと言っています.
//kkksc 03こっそり言います:あなたは勝手に1つの数字を出力して、すべて1/2の確率があります.しかし、これは楽多試合で、あなたが見てやる価値がありますか.だから一番正解を考えたい.
 
F.Alexのランチ
単点時間:3.0 sec
メモリ制限:64 MB
スティーブとアレックスは毎日昼食に何を食べるか悩んでいます.食べ物が多すぎて、とてもおいしいです.何を食べるかという問題を解決するために、アレックスは食事の前にアンケートを発表し、親友に今日一番食べたい食べ物を選ばせ、アレックスはアンケートの結果に基づいて何を食べるかを確定することにした.
各アンケートは1つの食べ物しか収集されず、各食べ物は1つの数字numで表されています.Alexはアンケートに出た回数がアンケート総数の半分を超える数字を選んで今日の昼食を決めます
入力フォーマット
単一グループ入力、各グループ2行
1行目に整数N(1≦N≦2)がある×107)
2行目にはN個の整数num(num≦1018)があり、各アンケートの数字を表す
出力フォーマット
出現回数がN 2を超える整数を出力する
サンプル
Input

4
1 1 1 2

Output

1

Input

5
2 2 3 3 3

Output

3

ヒント
各グループのデータに必ず条件を満たす数があることを保証します.問題のメモリ制限に注意してください.
 
2つの問題は大体一致しているので,私は一緒に書いた.今日は5回目の学校試合で、もちろん大学1年生です.彼らが問題を書いているのを見て、私も書いてみたいと思っています.結局私が勝手に選んだ問題は穴問題(このF問題)だった.私はmapで書いた、wa;データが1 e 18であることを発見しました.はい、long long、tleを変更します.私は行きます.無秩序mapを試してみます.やっと漂いました(2.7 s/3 s).
それからvectorで書いてみました.mle、はい、わかりました.この問題はすべてのデータを保存することはできません.穴!出題者はブログでこの問題の正解を紹介した.https://www.cnblogs.com/Friends-A/p/11368412.html?tdsourcetag=s_pcqq_aiomsg
ムーア投票アルゴリズムを使っているので、見てみることをお勧めします.
次は洛谷のコードです.

#include 
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

int main()
{
    //ios::sync_with_stdio(0);
    int n, x, res, ans;
    scanf("%d", &n);
    res = ans = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        if(!res)
            ans = x;
        if(x == ans)
            res++;
        else res--;
    }
    printf("%d
", ans);

    return 0;
}

以下は積分試合用無秩序mapのコードです.

#include 
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define P pair
const int MAXN = 1e5 + 7;
unordered_map  mp;

int main()
{
    ios::sync_with_stdio(0);
    ll n, x;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>x;
        mp[x]++;
    }
    unordered_map  :: iterator it;
    P pr;
    pr.second = 0;
    for(it = mp.begin(); it != mp.end(); it++)
    {
        if(it->second > pr.second) pr.second = it->second, pr.first = it->first;
    }
    cout<