2020-11-24

求众数【用STL中的map和set实现】

TimeLimit:2000MS MemoryLimit:128000KB
64-bit integer IO format:%lld
Problem Description
Input
输入多组数据
每组数据的第一行是一个n，表示有n个操作（n<=100000）
接下来有n行，有两种操作
1 x 表示添加数字x (x是正整数且在int范围内)
2 输出添加了的数中出现最多次的数，如果有多个，则依次从小到大输出

其中2操作不超过总操作数的1/8。

Output
每个2操作输出出现最多次的数，如果有多个，则依次从小到大输出
SampleInput
6
1 1
2
1 2
2
1 2
2
SampleOutput
1
1 2
2

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <bitset>
#include <ctime>
#include <fstream>
#include <limits.h>
#include <numeric>

using namespace std;

#define F first
#define S second
#define mian main
#define ture true

#define MAXN 1000000+5
#define MOD 1000000007
#define PI (acos(-1.0))
#define EPS 1e-6
#define MMT(s) memset(s, 0, sizeof s)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef stringstream sstm;
const int INF = 0x3f3f3f3f;

struct node{
    int sum,x;
    bool operator <(const node &b)const{
        if(sum == b.sum)
            return x < b.x;
        else
            return sum > b.sum;
    }

};

map<int,int >m;
set<node>s;
set<node>::iterator it;

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int n;
    int t, x, e;
    while(~scanf("%d", &n)){
        s.clear();
        m.clear();
        while(n--){
            scanf("%d", &t);
            if(t== 1){
                scanf("%d", &x);
                m[x]++;
                s.insert((node){m[x], x});
            }else {
                if(!s.empty()){
                    e = s.begin()->sum;
                    int flag = 0;//此处定义一个flag，用于判断是否是第一个输出
                    for(it = s.begin(); it != s.end(); it++){
                        if(it->sum == e){
                            if(flag++)
                                printf(" ");
                            printf("%d", it->x);
                        }

                    }
                    puts("");
                }
            }
        }
    }

}

注意点：
1.多组输入时，记得将前一组的set和map清空。
2.map<int, int > m;
int x;
m[x]++表示记录x出现的次数。【初始时，m就相当于一个全零数组】
3. s.insert((node){m[x], x}); 注意这个insert的写法。
4.注意这个结构体的定义，并在结构体中将小于符号改为大于符号。
struct node{
int sum,x;
bool operator <(const node &b)const{
if(sum == b.sum)
return x < b.x;
else
return sum > b.sum;
}
5.请注意，这里不能直接让it=s.begin();
或者直接输出s.begin()->x;因为众数可能不止一个，这样输出的话就一定只输出一个。