สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอีกหมายเลข H. H คือสุขภาพของศัตรู เรามีอาวุธ n ชนิด และพลังทำลายล้างของอาวุธนั้นคือ A[i] สามารถใช้อาวุธต่าง ๆ เพื่อฆ่าศัตรูได้ เราไม่สามารถใช้อาวุธชนิดเดียวกันได้สองครั้งติดต่อกัน เราต้องนับขั้นต่ำว่าเราจะใช้อาวุธสังหารศัตรูได้กี่ครั้ง
ดังนั้น ถ้าอินพุตเป็น A =[2, 1, 7]; H =11 แล้วเอาท์พุตจะเป็น 3 เพราะถ้าเราใช้อาวุธที่มีพลังโจมตี 7 แล้วใช้ 2 แล้วใช้ 7 อีกครั้ง เราจะฆ่าศัตรูได้
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
sort the array A n := size of A x := (A[n - 1] + A[n - 2]) return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int H){
sort(A.begin(), A.end());
int n = A.size();
int x = (A[n - 1] + A[n - 2]);
return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1];
}
int main(){
vector<int> A = { 2, 1, 7 };
int H = 11;
cout << solve(A, H) << endl;
} อินพุต
{ 2, 1, 7 }, 11 ผลลัพธ์
3
