PAT-A 真题 – 1054 The Dominant Color

Behind the scenes in the computer's memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution $M$ by $N$ (for example, $800\times 600$), you are supposed to point out the strictly dominant color.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: $M$ ($\le 800$) and $N$ ($\le 600$) which are the resolutions of the image. Then $N$ lines follow, each contains $M$ digital colors in the range [0,224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print the dominant color in a line.

Sample Input:

5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24

Sample Output:

24

题目大意：第一行给定图片的长宽，接着给出这个图片每一个像素点的像素值，找到多数（大于整幅图片的一半）像素值。

这道题应当使用map存储，否则数组开太大会栈溢出。不要使用cin和cout，测试点2会超时。

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;

int main(){
  map<int, int> P;
  int m, n, max_times = 0, max_color = 0;
  scanf("%d %d", &m, &n);
  for(int i = 0; i < m * n; i++){
    int color;
    scanf("%d", &color);
    P[color]++;
    if(P[color] > max_times){
      max_times = P[color];
      max_color = color;
    }
  }
  printf("%d", max_color);
  return 0;
}