問題
個の魔法があり、番目の魔法を唱えると気温が度上がって度下がる。全ての魔法を1回ずつ唱えるとき、この間の気温の最大値を最小化せよ。
解法
まずであるものについての昇順に、次にであるものについて任意の順番に、最後にであるものについての降順に使用していけば良い。
であるものについての昇順に使用すれば良いことはわかりやすいが、であるものについての降順に使用すれば最善となることについては、逆から見た状況を考えると良い。最後の温度から考え始めてであるものを用いて気温の最大値を最小化するのは、最初の気温からであるものを用いて最小化するのと変わらない状況である。
反省
1時間12分(0WA)でAC。1時間考察したがコードを書く段階には到達せず、結局1行も書かないまま解説を見ることになった。
これが解けないのはちょっとつらいところ。との大小関係で場合分けして考えることはしていたが、であるものについてどういう順番で使用すれば最善なのかがわからなかった。逆から見るという発想が完全に抜けてしまっていたとは……。そうでなくとも大きいが来ればそれ以降はその中に変化が収まってしまうみたいなところは考えていたのになぁ。残念。
コード
#include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { ll N; cin >> N; vector<pair<ll, ll>> lesser, equal, greater; for (ll i = 0; i < N; i++) { ll a, b; cin >> a >> b; if (a > b) { greater.emplace_back(a, b); } else if (a == b) { equal.emplace_back(a, b); } else { lesser.emplace_back(a, b); } } sort(lesser.begin(), lesser.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) { return lhs.first < rhs.first; }); sort(greater.begin(), greater.end(), [&](pair<ll, ll>& lhs, pair<ll, ll>& rhs) { return lhs.second > rhs.second; }); ll ans = 0, curr = 0; for (auto p : lesser) { curr += p.first; ans = max(ans, curr); curr -= p.second; } for (auto p : equal) { curr += p.first; ans = max(ans, curr); curr -= p.second; } for (auto p : greater) { curr += p.first; ans = max(ans, curr); curr -= p.second; } cout << ans << endl; }