โปรแกรม C++ นับจำนวนปัญหาสามารถแก้ไขได้จากด้านซ้ายหรือด้านขวาของรายการ

สมมติว่าเรามีอาร์เรย์ 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