526互联

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

发布时间 2023-10-21 20:30:13作者: zsxuan

你非常喜欢豚鼠。每个笼子可以住两只豚鼠，且你不想把每个笼子放入不同性别的豚鼠。豚鼠只有两种性别。假设你买到豚鼠时并不知道性别，只有医生能够分辨。

接下来的 \(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;
}