すぬけのお誕生日コンテスト B - Snuke
問題(というかトップページ)
解法
's' を消せるので, 's' が連続した部分文字列の直後の文字 c が c < 's' を満たすなら, なるべくその 's' は消したほうが得になります。逆に, c > 's' を満たすなら, なるべく消したくないですが, 消さないといけないとしたら, 辞書順に影響を与えにくい後ろから消していくのが良いです。
int main() { cin.tie(0); ios::sync_with_stdio(false); int k; cin >> k; string t, ans; cin >> t; int n = t.size(); int cur = 0; while (cur < n) { if (t[cur] == 's') { int i = cur; while (i < n && t[i] == 's') i++; if (t[i] < 's') { if (i-cur > k) { for (int j = 0; j < i-cur-k; j++) ans += 's'; k = 0; } else { k -= i-cur; } } else { ans += t.substr(cur, i-cur); } cur = i; } else { ans += t[cur++]; } } string ret; reverse(ans.begin(), ans.end()); for (char c : ans) { if (c == 's' && k > 0) { k--; } else { ret += c; } } reverse(ret.begin(), ret.end()); cout << ret << endl; return 0; }