[ICPC 2021 Jakarta R] Uniform Maker

chen_zhe · 2026-03-04 14:23:43 · 题解

这是官方题解的 AI 中文翻译。

对于每个位置，我们都应该保留出现频率最高的字符。设 f_i 为第 i 个位置上所有字符中出现次数最多的那个字符的出现次数。这个问题的答案是 \sum_{i=1}^M (N - f_i)。

#pragma GCC optimize "-O2"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

int N, M;
string S[maxn];

int main(int argc, char *argv[]) {
  cin >> N >> M;
  for (int i = 0; i < N; ++i)
    cin >> S[i];

  int ans = 0;
  for (int j = 0; j < M; ++j) {
    map<char, int> m;
    for (int i = 0; i < N; ++i)
      ++m[S[i][j]];
    int hi = 0;
    for (auto p : m)
      hi = max(hi, p.second);
    ans += N - hi;
  }

  cout << ans << endl;

  return 0;
}