Chương trình C ++ để đếm số vấn đề có thể được giải quyết từ cuối danh sách bên trái hoặc bên phải

Giả sử chúng ta có một mảng A với n phần tử và một số k khác ở đó. Xem xét có n vấn đề trong một cuộc thi. Kỹ năng giải quyết vấn đề của Amal là k. Amal luôn giải quyết vấn đề từ bất kỳ đầu nào trong danh sách. Và Người không thể giải quyết vấn đề có độ khó lớn hơn k. Anh ta dừng lại khi độ khó của vấn đề bên trái và bên phải lớn hơn k. Chúng ta phải đếm xem anh ta có thể giải quyết được bao nhiêu vấn đề. A [i] đại diện cho khó khăn của vấn đề thứ i.

Vì vậy, nếu đầu vào là A =[4, 2, 3, 1, 5, 1, 6, 4]; k =4, thì kết quả đầu ra sẽ là 5, bởi vì ban đầu giải bài toán trái nhất với 4, sau đó giải bài nhất bên phải với 4, sau đó không thể giải bài toán bên phải nữa, rồi từ trái, giải bài toán khó 2, 3 và 1. Trong tổng số 5 vấn đề có thể được giải quyết.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4

Đầu ra

5