微妙なコーナーケースに注意
問題概要
の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか?
- ペアとなるカードの数値の差は 1 以下
制約
考えたこと
一瞬、
- 値が等しいペアを作れるだけ作って
- 残った中で値が小さい方から順にペアリングしていく
という方法が最適解を導きそうな気がしてしまう。しかしこれは嘘で、以下のようなケースがある:
この場合は、(1, 2) と (2, 3) の 2 ペア作れる。しかし (2, 2) をペアリングしてしまうと (1, 3) をペアにできないのだ。
正しくは
正しくは、数列 を「0」の部分で区切った区間ごとに考えたとき、
ということがいえる (厳密な証明は数学的帰納法など)。逆にこれらが最適であることも明らか。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long long> a(N); for (int i = 0; i < N; ++i) cin >> a[i]; long long res = 0, sum = 0; for (int i = 0; i < N;) { int j = i; while (j < N && a[j]) sum += a[j++]; res += sum / 2; sum = 0; i = j+1; } cout << res << endl; }