给一个长为 \(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;
}