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