AtCoder Beginner Contest 027 D - ロボット
ぐぬぬ…
解法
スライドがわかりやすいのでほとんどそのままです。
abc027 from AtCoder Inc.
www.slideshare.net一応すこし補足すると,最終的な答えがソートした際の(後半そのまま) - (前半そのまま) で良いのは, 後半を + 方向に進むのに,前半を - 方向に進むのに割り当てているからですね。
string s; int N = 0; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> s; N = s.size(); vector<int> plus; int cur = 0; for (int i = N-1; i >= 0; i--) { if (s[i] == '+') cur++; else if (s[i] == '-') cur--; else plus.push_back(cur); } sort(plus.begin(), plus.end()); int ans = 0; int M = plus.size(); for (int i = 0; i < M/2; i++) ans -= plus[i]; for (int i = 0; i < M/2; i++) ans += plus[i+M/2]; cout << ans << endl; return 0; }