Giả sử chúng ta có một mảng A với n phần tử và một số k khác. Xét có n bài toán trong một cuộc thi. Kỹ năng giải bài của Amal là k. Amal luôn giải bài từ một trong hai đầu của danh sách. Và anh ta không thể giải bài nào có độ khó lớn hơn k. Anh ta dừng lại khi bài toán bên trái và bên phải đều có độ khó lớn hơn k. Chúng ta phải đếm xem anh ta có thể giải bao nhiêu bài. A[i] biểu thị độ khó của bài thứ i.
Ví dụ, nếu đầu vào là A = [4, 2, 3, 1, 5, 1, 6, 4]; k = 4, thì đầu ra sẽ là 5, vì ban đầu giải bài bên trái nhất độ khó 4, sau đó bài bên phải nhất độ khó 4, rồi không thể giải bài bên phải nữa, sau đó từ trái, giải các bài độ khó 2, 3 và 1. Tổng cộng 5 bài có thể giải được.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của A l := 0 r := n - 1 for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if A[i] <= k và l giống i, thì: (tăng l lên 1) while A[r] <= k, do: (giảm r đi 1) if l giống n, thì: return n Ngược lại return n - 1 - r + l
Ví dụ
Xem 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