hdu 1800 Flying to the Mars 詳細題解 哈希

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1800

這道題目是道哈希的簡單題，主要難度在于怎樣将問題抽象畫。

對于每一組資料，我要求它最少需要幾把掃帚。

我們把2 4 5 6 4這組輸入排序，變成了2 4 4 5 6，每一次取最長的一個遞增序列，取的次數就是我們需要的答案，請仔細想想，若輸入為2 4 5 6，那我們隻需要一把掃帚就能裝下所有人，但我們輸入2 4 4 5 6，就需要兩把了，我們每次都取了一個遞增序列，為什麼開始要一把，現在要兩把呢？因為我還有一個人的等級也是4，而我已經有一個4而且序列必須遞增，是以同樣的等級4我隻能取一個人。另一個隻好留着下次取了。是以這個問題就抽象成了：求一組數中出現頻率最大的那個數出現的次數！

這樣想是不是很簡單了？

每次輸入一個數i，數組mp[i]++一次，之後把i的範圍全部周遊一遍，把mp數組最大的一個元素輸出就行了。（若對stl裡面的map不了解可以自己百度一下）

貼個完整的代碼：

#include <iostream>
#include <string>
#include <stdio.h>
#include <map>

using namespace std;

int main()
{
    int n,max;
    map<int,int>mp;
    int num;
    while(scanf("%d",&n)!=EOF){
        mp.clear();
        max=0;
        while(n--){
            scanf("%d",&num);
            mp[num]++;
            if(mp[num]>max){
                max=mp[num];
            }
        }
        printf("%d\n",max);
    }
    return 0;
}