สมมติว่าเรามีอาร์เรย์ A ขนาด n และตัวเลข H H คือพลังชีวิตศัตรู มีอาวุธ n ชิ้น กำลังทำลายของอาวุธ i คือ A[i] ใช้อาวุธต่างกันฆ่าศัตรูได้ ไม่สามารถใช้อาวุธเดียวกัน 2 รอบติดกัน นับรอบน้อยสุดที่ใช้อาวุธฆ่าศัตรู
เช่น ถ้าอินพุตคือ A = [2, 1, 7]; H = 11 เอาต์พุตจะเป็น 3 เพราะใช้อาวุธ 7 แล้ว 2 แล้ว 7 อีกครั้งฆ่าศัตรูได้
ขั้นตอนการแก้ปัญหา
เรียงลำดับ A n := ขนาดของ 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
