C - T-shirts Editorial by nu50218
二分探索で解くことができます。\(T\)シャツが多いことで損はなく、また \(N\) 枚購入すると必ず条件を満たすように行動できるのはあきらかです。したがってはじめ ok = N, ng = -1
として二分探索を行い、 ok
の値を出力します。
チェック関数内では、 \(O(N)\) 時間かけてシミュレートして判定します。ロゴ入りのTシャツは 1
2
どちらのイベントでも着用できて、一方で無地のTシャツは 1
でしか着用できません。したがって、1
で無地のTシャツが余っているときはそちらから使うべきです。
以上の方針で、全体で \(O(N \log N)\) 時間で解くことができます。
C++による実装例:
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
string S;
cin >> S;
int ng = -1;
int ok = N;
auto check = [&](int mid) -> bool {
const int muji_max = M;
const int logo_max = mid;
int muji = muji_max;
int logo = logo_max;
for (int i = 0; i < N; i++) {
if (S[i] == '0') {
muji = muji_max;
logo = logo_max;
continue;
}
if (S[i] == '1') {
if (muji > 0) {
muji--;
continue;
}
if (logo > 0) {
logo--;
continue;
}
return false;
}
if (S[i] == '2') {
if (logo > 0) {
logo--;
continue;
}
return false;
}
}
return true;
};
while (ok - ng > 1) {
int mid = midpoint(ng, ok);
(check(mid) ? ok : ng) = mid;
}
cout << ok << endl;
}
posted:
last update: