https://codeforces.com/contest/1283/problem/E
解説
https://codeforces.com/contest/1283/submission/67851492
最小と最大別々に考えよう。
DPでうまいことやる?
最小のときは、同じ値は特に考える必要はないので、1つにまとめておく。
これで「dp[i] := i番目までまとめたときのグループの最小値」を更新する。
AをソートしておくことでこのDPを更新できる。
貪欲にやれそう。
最大のときは、-1して悪くならない限り、-1をすればいい。
こうすると+1での最適化ができないので、+1して悪くならない限り、+1をする。
これでできているグループの個数を数えると最大。
int N, A[201010]; //--------------------------------------------------------------------------------------------------- int dp[201010]; int solve1() { vector<int> v; rep(i, 0, N) v.push_back(A[i]); v.erase(unique(all(v)), v.end()); int n = v.size(); rep(i, 0, n + 1) dp[i] = inf; dp[0] = 0; rep(i, 0, n) { chmin(dp[i + 1], dp[i] + 1); if (i + 1 < n) { if(v[i + 1] - v[i] <= 2) chmin(dp[i + 2], dp[i] + 1); } if (i + 2 < n) { if (v[i + 2] - v[i] <= 2) chmin(dp[i + 3], dp[i] + 1); } } return dp[n]; } //--------------------------------------------------------------------------------------------------- int solve2() { map<int, int> cnt; rep(i, 0, N) cnt[A[i]]++; rep(i, 0, N) { int a = A[i]; if (cnt[a - 1] == 0) { cnt[a - 1]++; cnt[a]--; A[i] = a - 1; } } rrep(i, N - 1, 0) { int a = A[i]; if (cnt[a + 1] == 0) { cnt[a + 1]++; cnt[a]--; A[i] = a + 1; } } set<int> se; rep(i, 0, N) se.insert(A[i]); int ans = se.size(); return ans; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; sort(A, A + N); int mi = solve1(); int ma = solve2(); cout << mi << " " << ma << endl; }