你非常喜欢豚鼠。每个笼子可以住两只豚鼠，且你不想把每个笼子放入不同性别的豚鼠。豚鼠只有两种性别。假设你买到豚鼠时并不知道性别，只有医生能够分辨。
接下来的 \(n\) 天方案中，若第 \(i\) 天为 \(1\) ，你买入一只豚鼠；若为 \(2\) ，你请医生分辨你的豚鼠性别。
给出方案，你最少需要准备多少个笼子。
显然维护 \(cnt\) 为当前购入了多少豚鼠，\(sure\) 为当前有多少豚鼠确定了性别。于是当前需要的笼子为 \(1 + \lfloor \frac{sure}{2} \rfloor + (cnt - sure)\) 。
- 对于 \(unsure = cnt - sure\) ，每个豚鼠需要单独分配一个笼子
- 对于 \(sure > 0\) 。
- 若为奇数，则可以总保留一个豚鼠，每多两只豚鼠，则在三只里有两只性别相同。答案为 \(1 + \lfloor \frac{sure}{2} \rfloor\) 。
- 若为偶数，保留一直豚鼠，当考虑到最后一只豚鼠时，最坏情况为和保留的豚鼠性别不同。答案为 \(2 + \frac{n - 2}{2} = 1 + \lfloor \frac{sure}{2} \rfloor\) 。
- 这个原理必须保证 \(sure >= 1\) ，存在用于保留的豚鼠。否则会多出 \(1\) 的贡献。
view
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int n; std::cin >> n;
int ans = 0, cnt = 0, sure = 0;
for (int i = 1; i <= n; i++) {
int x; std::cin >> x;
if (x == 1) cnt += 1;
else sure = cnt;
ans = std::max(ans, (sure > 0 ? 1 + (sure / 2) : 0) + cnt - sure);
}
std::cout << ans << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}