Bài toán: n nhiệm vụ, thời gian A[i] (đã sắp xếp tăng). Amal chọn tối đa k nhiệm vụ làm trong x thời gian (x < min(A)). Tìm tổng thời gian tối thiểu.
Chiến lược tối ưu: Dùng x cho k nhiệm vụ lâu nhất (cuối mảng). Làm n-k nhiệm vụ đầu theo thời gian gốc.
Code C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int k, int x) {
int n = A.size();
long long total = 1LL * k * x; // k nhiệm vụ nhanh
for (int i = 0; i < n - k; i++)
total += A[i]; // n-k nhiệm vụ đầu
return total;
}
int main() {
vector<int> A = {3, 6, 7, 10};
int k = 2, x = 2;
cout << solve(A, k, x) << endl; // 3+6+2+2 = 13
return 0;
}
Kết quả
13