สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอาร์เรย์อื่นๆ อีก 2 อาร์เรย์ k และ x งาน ith ต้องใช้เวลา A[i] ให้เสร็จ A ที่ให้มาจะถูกจัดเรียงแบบไม่ลดทอน Amal ใช้เวลามากที่สุด k งานและทำแต่ละงานในหน่วย x หน่วยของเวลาแทนที่จะเป็น A[i] (x <ต่ำสุดของ A[i] ทั้งหมด) เราต้องหาเวลาขั้นต่ำที่จำเป็นในการทำงานของอามาลให้เสร็จ Amal ไม่สามารถทำงานมากกว่าหนึ่งงานพร้อมกันได้
ดังนั้น หากอินพุตเป็น A =[3, 6, 7, 10]; k =2; x =2 จากนั้นผลลัพธ์จะเป็น 13 เนื่องจากตัวเลือกที่ดีที่สุดคือทำงานที่สามและสี่ โดยใช้เวลา x =2 ครั้งในแต่ละงานแทนที่จะเป็น A[2] และ A[3] จากนั้นคำตอบคือ 3 + 6 + 2 + 2 =13
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
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
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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;
} อินพุต
{ 3, 6, 7, 10 }, 2, 2 ผลลัพธ์
13
