คำอธิบายปัญหา
สมมติว่าเรามีอาร์เรย์ A n องค์ประกอบ และค่า c มีโปรแกรมเขียนข้อความขี้เกียจ ถ้าไม่พิมพ์ต่อเนื่อง c วินาที ตัวอักษรที่เขียนไว้จะหายหมด A[i] คือเวลาที่พิมพ์ตัวอักษรตัวที่ i ต้องการหาจำนวนตัวอักษรที่เหลือบนหน้าจอหลังพิมพ์ครบ n ตัว
ตัวอย่าง: A = [1, 3, 8, 14, 19, 20]; c = 5 ผลลัพธ์คือ 3 เพราะ:
- วินาที 8 มี 3 ตัวอักษรบนหน้าจอ
- หายหมดที่วินาที 13
- วินาที 14 และ 19 พิมพ์เพิ่ม 2 ตัว
- วินาที 20 พิมพ์อีก 1 ตัว รวมเหลือ 3 ตัว
ขั้นตอนการแก้ปัญหา
s := 1
n := ขนาดของ A
สำหรับ i := 1 ถึง n-1:
ถ้า (A[i] - A[i-1]) <= c: เพิ่ม s ขึ้น 1
มิฉะนั้น: s := 1
คืนค่า s
ตัวอย่างโค้ด 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;
}
อินพุต
{ 1, 3, 8, 14, 19, 20 }, 5
เอาต์พุต
3
