Codeforces Round 857 (Div. 2) - B. Settlement of Guinea Pigs (1000)

B. Settlement of Guinea Pigs

나만 문제를 이해하기 어려운지 모르겠는데, 예시를 꼼꼼히 읽어봐야 완전히 이해할 수 있었다.

---

$U$을 아직 성별을 모르는 기니피그라고 하자.

일단 $x=1$ 이라면 $U \coloneqq U+1$

$x=2$ 라면 그걸 모두 성별을 아는 것으로 변경하고, 이 개수를 $K$ 라 하자.

$U$인 상태에선 항상 하나의 우리에 들어가있어야 하고, $K$에 대해서는 $\left\lceil \dfrac{K}{2} \right\rceil$ 개의 우리가 필요하다.

최악의 경우를 상정하면 항상 male, female, male … 순으로 성별이 결정되야하고 결국 cage는 $\left\lceil \dfrac{K}{2} \right\rceil$ 개가 필요해지기 때문이다.

그런데 cage는 한번 사면 다시 없어지지 않으므로 계속 정답의 최대값을 다음과 같이 갱신한다.

$\text{ans}=\text{Max}\left( ans, k+\left\lceil \dfrac{t}{2} \right\rceil \right)$

에디토리얼 정해 코드 첨부한다.

void solve() {
    int n;
    cin >> n;
    int known = 0, unknown = 0;
    int need = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == 1) ++unknown;
        else {
            known += unknown;
            unknown = 0;
        }
        need = max(need, unknown + (known ? known / 2 + 1 : 0));
    }
    cout << need << endl;
}