Mã C ++ để tìm thời gian tối thiểu cần thiết để thực hiện tất cả các tác vụ

Giả sử chúng ta có một mảng A với n phần tử, và hai mảng khác k và x. Nhiệm vụ thứ i mất A [i] thời gian để hoàn thành. A đã cho được sắp xếp theo kiểu không giảm. Amal nhận nhiều nhất k nhiệm vụ và thực hiện mỗi nhiệm vụ trong x đơn vị thời gian thay vì A [i]. (x

Vì vậy, nếu đầu vào là A =[3, 6, 7, 10]; k =2; x =2, thì đầu ra sẽ là 13, bởi vì tùy chọn tốt nhất sẽ là thực hiện nhiệm vụ thứ ba và thứ tư, dành x =2 thời gian cho mỗi nhiệm vụ thay vì A [2] và A [3]. Khi đó câu trả lời là 3 + 6 + 2 + 2 =13.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

x := k * x
n := size of A
for initialize i := 0, when i < n - k, update (increase i by 1), do:
   t := A[i]
   x := x + t
return x

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k, int x){
   x = k * x;
   int n = A.size();
   for (int i = 0; i < n - k; i++){
      int t = A[i];
      x += t;
   }
   return x;
}
int main(){
   vector<int> A = { 3, 6, 7, 10 };
   int k = 2;
   int x = 2;
   cout << solve(A, k, x) << endl;
}

Đầu vào

{ 3, 6, 7, 10 }, 2, 2

Đầu ra

13