题解 P6367 【[COCI2006-2007#6] PRASE】

一扶苏一 · 2020-04-12 00:53:22 · 题解

Analysis

简单模拟，用 std::map 存一下每个孩子取到的食物份数，设当前已经取了 i 份食物，则取第 i + 1 份食物时，其他人取到的食物总数就是 i - x，其中 x 是取第 i + 1 份食物的孩子已经取的食物份数。

Code

#include <map>
#include <string>
#include <iostream>

int n;
std::map<std::string, int> mp;

int main() {
  std::cin >> n;
  int ans = 0;
  std::string tmp;
  for (int i = 0; i < n; ++i) {
    std::cin >> tmp;
    int k = i - mp[tmp];
    if (mp[tmp]++ > k) ++ans;
  }
  std::cout << ans << std::endl;
  return 0;
}