1471A - Strange Partition
05 Jan 2021 — Tags: greedy — URL- Max: Leave the array as it is.
- Min: Merge the array into an element.
Intuitively, by summing the entire array into an element, we reduce the increasing effect of the ceil function.
Time complexity: $O(n)$
Memory complexity: $O(n)$
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll ceil(ll a, ll b) { return (a + b - 1) / b; }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, x;
cin >> n >> x;
vector<ll> a(n);
for (auto &ai : a)
cin >> ai;
ll min = ceil(accumulate(begin(a), end(a), 0LL), x);
ll max = 0;
for (auto ai : a)
max += ceil(ai, x);
cout << min << " " << max << endl;
}
return 0;
}