สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ และอีกตัวเลข k หนึ่ง ต้องการมีโจทย์ n ข้อในการแข่งขัน ทักษะการแก้โจทย์ของอมลคือ k อมลแก้โจทย์จากปลายซ้ายหรือขวาของรายการเสมอ และเขาไม่สามารถแก้โจทย์ที่ความยากมากกว่า k ได้ เขาหยุดเมื่อโจทย์ทั้งสองข้างมีความยากมากกว่า k เราต้องนับว่าเขาแก้โจทย์ได้กี่ข้อ A[i] แทนความยากของโจทย์ข้อที่ i
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [4, 2, 3, 1, 5, 1, 6, 4]; k = 4 ผลลัพธ์จะได้ 5 เพราะเริ่มแก้ข้อซ้ายสุด 4 แล้วขวาสุด 4 แล้วขวาแก้ไม่ได้ แล้วจากซ้ายแก้ 2, 3, 1 รวม 5 ข้อ
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ A l := 0 r := n - 1 สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: ถ้า A[i] <= k และ l เท่ากับ i แล้ว: (เพิ่ม l ขึ้น 1) ในขณะที่ A[r] <= k ทำ: (ลด r ลง 1) ถ้า l เท่ากับ n แล้ว: คืนค่า n มิฉะนั้น คืนค่า 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
