Giả sử chúng ta có một mảng A với n phần tử. Giả sử Amal leo cầu thang bên trong một tòa nhà nhiều tầng. Mỗi lần leo, bắt đầu đếm từ 1. Ví dụ, nếu anh ta leo hai cầu thang với 3 bậc và 4 bậc, anh ta sẽ nói các số như 1, 2, 3, 1, 2, 3, 4. Trong mảng A, các số đại diện cho số bậc mà Amal nói. Chúng ta phải đếm số cầu thang anh ta đã leo, cũng như in số bậc trong mỗi cầu thang.
Ví dụ, nếu đầu vào là A = [1, 2, 3, 1, 2, 3, 4, 5], thì đầu ra sẽ là 2, [3, 5]
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:
p = 0 n := kích thước của A for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if A[i] giống 1, thì: (tăng p lên 1) in p for khởi tạo i := 1, khi i < n, cập nhật (tăng i lên 1), do: if A[i] giống 1, thì: in A[i - 1] in A[n - 1]
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; void solve(vector<int> A) { int i, p = 0; int n = A.size(); for (i = 0; i < n; i++) { if (A[i] == 1) p++; } cout << p << endl; for (i = 1; i < n; i++) { if (A[i] == 1) cout << A[i - 1] << ", "; } cout << A[n - 1]; } int main() { vector<int> A = { 1, 2, 3, 1, 2, 3, 4, 5 }; solve(A); }Đầu vào
{ 1, 2, 3, 1, 2, 3, 4, 5 }Đầu ra
2 3, 5