数据严重过水
查看原帖
数据严重过水
726139
残阳如血楼主2024/9/27 20:57

下面代码复杂度是 O(n2)O(n^2) 的,显然会超时,理应在 8080 分上下,但是却可以 AC。

#include <bits/stdc++.h>
const int N = 1e5 + 10;

int n, m, t, a[N], cnt[N];
std::pair<int, int> offer[N];
std::unordered_set<int> ans;

int main() {
  std::cin >> n >> m >> t;
  for (int i = 0; i < m; ++i)
    std::cin >> offer[i].first >> offer[i].second;
  for (int i = 1; i <= t; ++i) {
    memset(cnt, 0, sizeof(cnt));
    for (int j = 0; j < m; ++j)
      if (offer[j].first == i) ++cnt[offer[j].second];
    for (int j = 1; j <= n; ++j) {
      if (cnt[j]) a[j] += 2 * cnt[j];
      else a[j] = std::max(a[j] - 1, 0);
      if (a[j] > 5) ans.insert(j);
      if (a[j] <= 3) ans.erase(j);
    }
  }
  std::cout << ans.size() << std::endl;
  return 0;
}
2024/9/27 20:57
加载中...