Editorial for Bedao Mini Contest 03 - COVIGAME
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; const int maxn = (int)1e5 + 7; int a[maxn], low[maxn], high[maxn], F[maxn], G[maxn]; vector <int> V[maxn]; int main() { freopen("COVIGAME.INP", "r", stdin); freopen("COVIGAME.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, k, mi = INT_MAX; cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i]; V[a[i]].push_back(i); if (i > 1) F[i] = F[i - 1] + (abs(a[i] - a[i - 1]) > k); } for (int i = 2; i <= n; ++i) if (a[i] == a[i - 1]) low[i] = low[i - 1]; else low[i] = i - 1; for (int i = n - 1; i > 0; --i) if (a[i] == a[i + 1]) high[i] = high[i + 1]; else high[i] = i + 1; F[n + 1] = F[n] + 1; for (int f = 1; f <= n; ++f) { int i = a[f]; if (G[i]) continue; for (int j = 1; j < (int)V[i].size(); ++j) G[i] += max(0, F[V[i][j] - 1] - F[V[i][j - 1] + 1]); if (V[i].size()) G[i] += F[V[i][0] - 1] + max(0, F[n] - F[V[i].back() + 1]); } for (int i = 1; i <= n; ++i) G[a[i]] += (low[i] && high[i] && abs(a[low[i]] - a[high[i]]) > k && a[i] != a[i - 1]); for (int i = 1; i <= n; ++i) mi = min(mi, G[a[i]]); int p = maxn; for (int i = 1; i <= n; ++i) if (G[a[i]] == mi) p = min(p, a[i]); cout << p; return 0; }
Comments