Cho mảng A kích thước n và số c. Trình soạn thảo xóa tất cả văn bản nếu không gõ phím trong c giây liên tiếp. A[i] là thời điểm gõ ký tự thứ i. Tìm số ký tự còn lại sau khi gõ hết.
Ví dụ
Với A=[1,3,8,14,19,20], c=5, đầu ra 3. Tại giây 8 có 3 ký tự. Xóa ở giây 13. Gõ thêm tại 14,19,20 → còn 3 ký tự.
Giải thuật
Khởi tạo s=1. Duyệt i=1..n-1: nếu A[i]-A[i-1] <= c thì s++, ngược lại s=1. Trả về s.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int c) {
int s = 1;
int n = A.size();
for (int i = 1; i < n; i++) {
if ((A[i] - A[i - 1]) <= c) s++;
else s = 1;
}
return s;
}
int main() {
vector<int> A = { 1, 3, 8, 14, 19, 20 };
int c = 5;
cout << solve(A, c) << endl;
}
Đầu vào / Đầu ra
Input: { 1, 3, 8, 14, 19, 20 }, 5
Output: 3