สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n และอีกจำนวนหนึ่งคือ k พิจารณาว่ามีปัญหา n ในการแข่งขัน ทักษะการแก้ปัญหาของ Amal คือ k Amal มักจะแก้ปัญหาจากจุดสิ้นสุดของรายการ และเขาไม่สามารถแก้ปัญหาที่ยากกว่า k ได้ เขาจะหยุดเมื่อความยากของปัญหาด้านซ้ายและขวามากกว่า k เราต้องนับว่าเขาแก้ปัญหาได้กี่ข้อ A[i] แสดงถึงความยากของปัญหา
ดังนั้น ถ้าอินพุตเป็น A =[4, 2, 3, 1, 5, 1, 6, 4]; k =4 แล้วผลลัพธ์จะเป็น 5 เพราะในตอนแรก แก้ปัญหาซ้ายสุดด้วย 4 แล้วขวาสุดคือ 4 แล้วแก้ปัญหาส่วนใหญ่ทางขวาไม่ได้แล้ว ต่อจากซ้าย แก้ปัญหาด้วยความยาก 2, 3 และ 1 ใน ปัญหาทั้งหมด 5 ข้อสามารถแก้ไขได้
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
n := size of A l := 0 r := n - 1 for initialize i := 0, when i < n, update (increase i by 1), do: if A[i] <= k and l is same as i, then: (increase l by 1) while A[r] <= k, do: (decrease r by 1) if l is same as n, then: return n Otherwise return n - 1 - r + l
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, int k) { int n = A.size(); int l = 0, r = n - 1; for (int i = 0; i < n; ++i) { if (A[i] <= k && l == i) ++l; } while (A[r] <= k) --r; if (l == n) return n; else return n - 1 - r + l; } int main() { vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 }; int k = 4; cout << solve(A, k) << endl; }
อินพุต
{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4
ผลลัพธ์
5