資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢在給定約束條件下完成所有工作的最短時間
概念
對於給定的一組具有不同時間需求的工作，假設有 k 個相同的分配者可用，並且我們還提供了分配者完成一個工作單位需要的時間。我們的任務是在以下約束條件下確定完成所有工作的最短時間。
第一個約束是分配者只能分配連續的工作。
例如，分配者可以分配陣列中位置 1 和 2 的工作，但不能分配位置 3 的工作。
第二個約束是兩個分配者不能共享（或共同分配）一個工作，這意味著一個工作不能部分分配給一個分配者，部分分配給另一個分配者。
輸入
k - 表示可用的分配者數量。
t - 表示分配者完成一個工作單位所需的時間
JOB[] - 表示一個數組，表示不同工作的時限需求。
輸入
k = 2, t = 4, JOB[] = {5, 6, 12}輸出
48
這裡，完成所有工作所需的最短時間是 48。
有兩個分配者可用。我們透過將 {5, 6} 分配給第一個分配者，將 {12} 分配給第二個分配者來獲得此時間。
輸入
k = 4, t = 5, JOB[] = {12, 6, 9, 15, 5, 9}輸出
75
我們透過分配 {12} {6, 9} {15} 和 {5, 9} 來獲得此時間
方法
現在，我們的思路是實現二分查詢。假設我們有一個函式（例如 isPossible()），它告訴我們是否可以在給定的時間和可用分配者數量內完成所有工作。在這裡，我們可以透過對答案進行二分查詢來解決這個問題。我們觀察到，如果二分查詢的中點是不可能的，那麼在後半部分搜尋，否則在前半部分搜尋。二分查詢最小時間的下界可以設定為 0。在這裡，上界可以透過新增所有給定的工作時間來獲得。
現在問題出現了，如何實現 isPossible()。我們可以使用貪心演算法實現此函式。因為我們想知道是否可以在給定的時間內完成所有工作，所以我們遍歷所有工作，並維護逐個將工作分配給當前分配者。同時，我們應該記住，工作必須在給定的時間限制內完成。噹噹前分配者花費的時間超過提供的時間時，建立一個新的分配者並開始將工作分配給它。我們觀察到，如果分配者的數量超過 k，則返回 false，否則返回 true。
示例
// C++ program to find minimum time to finish all jobs with
// given number of assignees
#include<bits/stdc++.h>
using namespace std;
// Shows utility function to get maximum element in job1[0..n1-1]
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;
}
// Now returns true if it is possible to finish jobs1[] within
// given time 'time1'
bool isPossible(int time1, int K1, int job1[], int n1){
// Here, cnt1 is count of current assignees required for jobs
int cnt1 = 1;
int curr_time1 = 0; // Indicates time assigned to current
//assignee
for (int i = 0; i < n1;){
// Now if time assigned to current assignee exceeds max1,
// increment count1 of assignees.
if (curr_time1 + job1[i] > time1) {
curr_time1 = 0;
cnt1++;
}
else { // Else add time of job to current time and move
// to next job.
curr_time1 += job1[i];
i++;
}
}
//Now returns true if count is smaller than k
return (cnt1 <= K1);
}
// Here, returns minimum time required to finish given array of
//jobs
// K1 --> number of assignees
// T1 --> Time required by every assignee to finish 1 unit
// n1 --> Number of jobs
int findMinTime(int K1, int T1, int job1[], int n1){
// Used to set start and end for binary search
// end provides an upper limit on time1
int end1 = 0, start1 = 0;
for (int i = 0; i < n1; ++i)
end1 += job1[i];
int ans1 = end1; // Used to initialize answer
// Determine the job that takes maximum time
int job_max1 = getMax(job1, n1);
// Perform binary search for minimum feasible time
while (start1 <= end1){
int mid1 = (start1 + end1) / 2;
// Now if it is possible to complete jobs 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);
}
// Driver program
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;
}輸出
75
351 次瀏覽
