526互联

Codeforces Round 694 (Div. 2) A. Strange Partition

发布时间 2023-10-12 16:22:18作者: zsxuan

给一个长为 \(n\) 的数组 \(a\) 和一个正整数 \(x\) 。你可以执行以下操作任意次：用两个相邻元素的和替换这两个元素。如 \([\cdots, a_i,a_{i+1},\cdots] \rightarrow [\cdots, a_i + a_{i+1},\cdots]\) 。

一个数组 \(b = [b_1, \cdots, b_k]\) 的美丽值定义为 \(\sum_{i=1}^{k} \lceil \frac{b_i}{x} \rceil\) 。

询问如何操作 \(a\) 能使 \(a\) 最后的美丽值最小和最大。输出最小值和最大值

显然 \(\lceil \frac{h}{x} \rceil + \lceil \frac{w}{x} \rceil \geq \lceil \frac{h + w}{x} \rceil\) 。

于是 \(a\) 的最小美丽值为 \(\lceil \frac{\sum_{i=1}^{n} a_i}{x} \rceil\) ，最大美丽值为 \(\sum_{i=1}^{n} \lceil \frac{a_i}{x} \rceil\) 。

view 
#include <bits/stdc++.h>
void solve(){
	int n, x; std::cin >> n >> x;
	long long sum_big = 0, sum_small = 0;
	for (int i = 1; i <= n; i++) {
		int a; std::cin >> a;
		sum_small += a;
		sum_big += (a + x - 1) / x;
	}
	sum_small = (sum_small + x - 1) / x;
	std::cout << sum_small << ' ' << sum_big << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}