在C ++中找到在给定约束下完成所有作业的最短时间

概念

对于具有不同时间要求的给定工作阵列，存在k个相同的受让人可用，并且我们还提供了受让人花费多少时间来完成一项工作。我们的任务是确定在以下约束条件下完成所有作业的最短时间。

第一个约束是只能为受让人分配连续的工作。
在此，例如，可以在阵列中位置1和2处而不是位置3处给受让人分配作业。
第二个约束是两个受让人不能共享（或共同指派）工作，这意味着不能将工作部分分配给一个受让人，也不能部分分配给另一受让人。

输入值

k-表示可用的受让人数量。

t-表示受让人完成一项工作所需的时间

JOB []-表示一个代表不同作业时间要求的数组。

输入值

k = 2, t = 4, JOB[] = {5, 6, 12}

输出结果

在这里，完成所有作业所需的最短时间为48。

有2个受让人。我们通过将{5，6}分配给第一位受让人，将{12}分配给第二位受让人来获得该时间。

输入值

k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}

输出结果

我们这次通过分配{12} {6，9} {15}和{5，9}

方法

现在的概念是实现二进制搜索。假设我们有一个函数（例如isPossible()）来指示我们是否有可能在给定的时间内和可用的受让人数量内完成所有作业。在这里，我们可以通过对答案进行二进制搜索来解决此问题。已经看到，如果不可能进行二进制搜索的中点，则在后半部分搜索，否则在前半部分搜索。可以将最小时间的二进制搜索的下限设置为0。在这里，可以通过将所有提供的作业时间相加来获得上限。

目前出现了如何实施的问题isPossible()。我们可以使用贪婪方法来实现此功能。因为我们想知道是否有可能在给定的时间内完成所有工作，所以我们遍历所有工作，并保持将工作逐一分配给当前的受让人。同时，我们应该记住，可以在给定的时限内分配工作。届时，当当前受让人占用的时间超过了提供的时间时，将生成一个新的受让人并开始为其分配工作。已经看到，如果受让人的数量大于k，则返回false，否则返回true。

示例

// C++ program to find minimum time to finish all 职位 with
//给定数量的受让人
#include<bits/stdc++.h>
using namespace std;
//最大元素
int getMax(int arr1[], int n1){
   int result1 = arr1[0];
   for (int i=1; i<n1; i++)
      if (arr1[i] > result1)
         result1 = arr1[i];
   return result1;
}
//完成job1 []，则返回true
//给定时间'time1'
bool isPossible(int time1, int K1, int job1[], int n1){
   //在这里，cnt1是作业所需的当前受让人的数量
   int cnt1 = 1;
   int curr_time1 = 0; // Indicates time assigned to current
   //受让人
   for (int i = 0; i < n1;){
      // Now if time assigned to current 受让人 exceeds max1,
      // increment count1 of 受让人s.
      if (curr_time1 + job1[i] > time1) {
         curr_time1 = 0;
         cnt1++;
      }
      else { // Else add time of job to current time and move
         //下一份工作。
         curr_time1 += job1[i];
         i++;
      }
   }
   //现在，如果count小于k，则返回true-
   return (cnt1 <= K1);
}
//所需的最短时间
//职位
// K1 --> number of 受让人s
// T1 --> Time required by every 受让人 to finish 1 unit
// n1 --> Number of 职位
int findMinTime(int K1, int T1, int job1[], int n1){
   //用于设置二进制搜索的开始和结束
   //end提供了时间上限
   int end1 = 0, start1 = 0;
   for (int i = 0; i < n1; ++i)
      end1 += job1[i];
   int ans1 = end1; // Used to initialize answer
   //确定需要最多时间的工作
   int job_max1 = getMax(job1, n1);
   //执行二进制搜索以获取最小可行时间
   while (start1 <= end1){
      int mid1 = (start1 + end1) / 2;
      // Now if it is possible to complete 职位 in mid time
      if (mid1 >= job_max1 && isPossible(mid1, K1, job1, n1)){
         ans1 = min(ans1, mid1); // Used to update answer
         end1 = mid1 - 1;
      }
      else
         start1 = mid1 + 1;
   }
   return (ans1 * T1);
}
//驱动程序
int main(){
   int job1[] = {12, 6, 9, 15, 5, 9};
   //int job1 [] = {5，6，12}; 
   int n1 = sizeof(job1)/sizeof(job1[0]);
   int k1=4, T1=5;
   //int k1 = 2，T1 = 4; 
   cout << findMinTime(k1, T1, job1, n1) << endl;
   return 0;
}

输出结果

基础教程