526互联

Codeforces Round 824 (Div. 2) B. Tea with Tangerines

发布时间 2023-09-09 21:11:05作者: zsxuan

有 \(n\) 块橘子皮，第 \(i\) 块大小为 \(a_i\) 。在一部操作中可以把一块橘子皮分成两块，即这块橘子皮为 \(x\) ，让 \(x\) 变为 \(y, z(x = y + z)\) 。

希望对于任意两块橘子皮，他们相差严格小于两倍。即两块中更小的为 \(x\) ，更大的为 \(y\) ，有 \(2x > y\) 。最少需要执行多少步操作。

观察一：显然关键在于最小块橘子皮，假设为第 \(x\) 块。只需保证其它橘子皮小于他的两倍，且中间过程不会出现比 \(a_x\) 更小的橘子皮即可。即 \(\forall i, i \neq x,\ s.t.\ 2a_x \leq a_i\) 且 \(a_i \geq a_x\) 。

观察二：可以贪心地考虑尽量分出最大块，将所有 \(a_i\) 分为 \(2a_x - 1\) 。

  • \(2a_x - 1 \mid a_i\) 时操作数为 \(\frac{a_i}{2a_x - 1} - 1\) 。操作数比块数少 \(1\) 。
  • \(2a_x \nmid a_i\) 时，操作数为 \(\lceil \frac{a_i}{2a_x - 1} \rceil - 1\) 。
    • 并不是真的切出最后余下的一块 \(r,(a_i \equiv r(\mod 2a_x - 1))\) ，可能存在 \(r < a_x\) 打乱全局。
    • 性质：逐渐分小时，最后一块为 \(2a_x - 1 + r,(1 \leq r < 2a_x - 1)\) 。考虑到取值范围在 \([2a_x + 0, 4a_x - 3]\) 。显然存在 \(h, w\) 满足 \(h + w = 2a_x - 1 + r\) 且 \(a_x \leq h,w \leq 2a_x - 1\) 。
    • 即考虑末尾反悔的合法性。（末尾反悔和中途反悔通常区分比较明显）

则答案为 \(\sum_{i = 1, i \neq x}^{n} (\lceil \frac{a_i}{2a_x} \rceil - 1) = \sum_{i = 1, i \neq x}^{n} (\lceil \frac{a_i}{2a_x} \rceil) - n + 1\)。

代入 \(x\) 也能符合，可化简为 \(\sum_{i = 1}^{n} (\lceil \frac{a_i}{2a_x} \rceil) - n\)

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	int x = std::min_element(a.begin() + 1, a.end()) - a.begin();
	long long ans = 0; for (int i = 1; i <= n; i++) if (i != x) {
		ans += (a[i] + (2 * a[x] - 1) - 1) / (2 * a[x] - 1);
	}
	std::cout << ans - n + 1 << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}