C++UCS301
Complexity Lab C++ Setup Visualizer
Practice arena
C++17·2 s·128 MB
SearchingIntermediate

Minimum feasible speed

Given workloads and h hours, find the smallest positive integer speed that completes every workload. A workload of x takes ceil(x / speed) hours.

Input

  • — The first line contains T.
  • — Each case contains n and h, followed by n positive workloads.

Output

Print the minimum feasible speed for each case.

Technique

binary search on answer

Target

O(n log max(workload))

Constraints & sample
  • 1 ≤ n ≤ h ≤ 200,000
  • 1 ≤ workload ≤ 10⁹

Sample input

3
4 8
3 6 7 11
5 5
30 11 23 4 20
5 6
30 11 23 4 20

Expected output

4
30
23
Review the concept

Before you submit

  • Test the smallest valid input and one awkward edge case.
  • Keep the solution within O(n log max(workload)).
  • Match spacing and line breaks exactly before checking 8 hidden cases.
main.cpp
Draft saved locally · 500 / 30,000
Ln 1, Col 1Spaces: 4UTF-8LFC++17

Visible testcases

Editable and stored only in this browser. Hidden judge cases never change.

Checking your session…

Run checks Sample · Submit checks 8 hidden cases

Run the sample first, then send your solution through 8 hidden cases.

Code runs in an isolated Judge0 environment. Drafts and custom visible cases stay on this device; submission metadata and progress sync to MongoDB.