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