[TIOJ] 1160. 3.動態眾數問題

題目連結:http://tioj.infor.org/problems/1160
其實只要記錄每個數字有多少個,跟紀錄一下當前的眾數是誰以及他的量,當插入一個數字使得他的數量大於原本的眾數時就更新一下眾數資訊,不過不能用array因為他的值域太大,所以不妨考慮用個hash_table(unordered_map)
#include <stdio.h>
#include <unordered_map>

using namespace std;

int main(){
	unordered_map<int, int> arr;
	int inp, which=0, size=0;
	scanf("%d",&inp);
	while(inp!=0){
		if(arr.find(inp) == arr.end()){
			arr[inp] = 1;
		}else{
			arr[inp] ++;
		}
		if(arr[inp]>size){
			which = inp;
			size = arr[inp];
		}else if(arr[inp]==size){
			which = (inp<which)?inp:which;
		}
		printf("%d %d\n",size, which);
		scanf("%d",&inp);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology