fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Utility function to get maximum element in job[0..n-1]
  5. int getMax(int arr[], int n) {
  6.     int result = arr[0];
  7.     for (int i = 1; i < n; i++)
  8.         if (arr[i] > result)
  9.             result = arr[i];
  10.     return result;
  11. }
  12.  
  13. // Returns true if it is possible to finish jobs[] within
  14. // given time 'time' using K robots
  15. bool isPossible(int time, int K, int job[], int n) {
  16.     int cnt = 1;         // Number of robots currently used
  17.     int curr_time = 0;   // Time assigned to the current robot
  18.  
  19.     for (int i = 0; i < n;) {
  20.         // If assigning job[i] to the current robot exceeds 'time', 
  21.         // increment the count of robots and reset curr_time
  22.         if (curr_time + job[i] > time) {
  23.             curr_time = 0;
  24.             cnt++;
  25.         } else {  // Else add time of job[i] to current robot's time
  26.             curr_time += job[i];
  27.             i++;
  28.         }
  29.     }
  30.  
  31.     // Returns true if count of robots used is <= K
  32.     return (cnt <= K);
  33. }
  34.  
  35. // Returns minimum time required to finish given array of jobs
  36. // K --> number of robots
  37. // T --> Time required by every robot to finish 1 unit of task
  38. // job[] --> Array representing time each job takes
  39. // n --> Number of jobs
  40. int findMinTime(int K, int T, int job[], int n) {
  41.     int end = 0, start = 0;
  42.     for (int i = 0; i < n; ++i)
  43.         end += job[i];  // Sum of all jobs is the upper limit for time
  44.  
  45.     int ans = end;  // Initialize answer with the upper limit
  46.     int job_max = getMax(job, n);  // Find the job that takes maximum time
  47.  
  48.     // Binary search for minimum feasible time
  49.     while (start <= end) {
  50.         int mid = (start + end) / 2;
  51.  
  52.         // If it is possible to finish jobs in 'mid' time with K robots
  53.         if (mid >= job_max && isPossible(mid, K, job, n)) {
  54.             ans = min(ans, mid);  // Update answer
  55.             end = mid - 1;        // Try for a smaller feasible time
  56.         } else {
  57.             start = mid + 1;      // Increase time if 'mid' is too small
  58.         }
  59.     }
  60.  
  61.     return (ans * T);  // Multiply by T to get the total time in units
  62. }
  63.  
  64. // Driver program
  65. int main() {
  66.     int job[] = { 10, 20, 30, 40, 50 };  // Array of job times
  67.     int n = sizeof(job) / sizeof(job[0]);  // Number of jobs
  68.     int k = 2;  // Number of robots
  69.     int T = 5;  // Time taken by each robot to move one unit of task
  70.  
  71.     cout << "Minimum time to complete all jobs: " << findMinTime(k, T, job, n) << " units" << endl;
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum time to complete all jobs: 450 units
https://ideone.com/lF2JV3
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!