โจทย์
แอปออกกำลังกายตัวหนึ่งมีคลาส StepTracker ซึ่งสร้างขึ้นพร้อมเป้าหมาย min_active วันหนึ่งจะนับเป็นวันที่แอ็กทีฟเมื่อจำนวนก้าวมีอย่างน้อยเท่ากับค่านี้ แทนที่จะเขียนคลาส ให้ประมวลผลการเรียกเมธอดในรูปลิสต์ของคำสั่งดังนี้
add N: บันทึกวันใหม่ที่เดินได้Nก้าว (ไม่มีเอาต์พุต)total: แสดงจำนวนก้าวรวมของทุกวันที่บันทึกไว้active: แสดงจำนวนวันที่บันทึกไว้ซึ่งเป็นวันที่แอ็กทีฟaverage: แสดงจำนวนก้าวเฉลี่ยต่อวัน ปัดเศษลงเป็นจำนวนเต็ม หรือ 0 ถ้ายังไม่มีวันที่บันทึกไว้best: แสดงจำนวนก้าวมากที่สุดในหนึ่งวัน หรือ 0 ถ้ายังไม่มีวันที่บันทึกไว้
จงเขียน step_tracker(min_active, operations)
อินพุต
min_active: จำนวนก้าวที่ทำให้วันหนึ่งเป็นวันที่แอ็กทีฟ
operations: คำสั่งต่าง ๆ ซึ่งประมวลผลตามลำดับ
เอาต์พุต
คืนค่าผลลัพธ์ของคำสั่งที่เป็นการสอบถาม ตามลำดับที่เกิดขึ้น
เงื่อนไข
1 ≤ min_active ≤ 100,000
0 ≤ จำนวนคำสั่ง ≤ 1,000
0 ≤ N ≤ 100,000
ตัวอย่าง
อินพุต:
min_active = 8000
operations = ["add 9000", "add 4500", "active", "add 12000", "total", "average", "best"]
ผลลัพธ์ที่คาดหวัง:
expected = [1, 25500, 8500, 12000]
อินพุต:
long long min_active = 8000;
std::vector<std::string> operations = {"add 9000", "add 4500", "active", "add 12000", "total", "average", "best"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {1, 25500, 8500, 12000};
อินพุต:
long min_active = 8000;
string[] operations = new string[] {"add 9000", "add 4500", "active", "add 12000", "total", "average", "best"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {1, 25500, 8500, 12000};
คำอธิบาย
หลังผ่านไปสองวัน มีเพียง 9000 ที่ถึง 8000 active จึงเป็น 1 จากนั้นผลรวมคือ 25500 ค่าเฉลี่ยคือ 25500 / 3 = 8500 และวันที่เดินมากที่สุดคือ 12000
อินพุต:
min_active = 5000
operations = ["average", "best", "add 5000", "add 4999", "active", "average"]
ผลลัพธ์ที่คาดหวัง:
expected = [0, 0, 1, 4999]
อินพุต:
long long min_active = 5000;
std::vector<std::string> operations = {"average", "best", "add 5000", "add 4999", "active", "average"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {0, 0, 1, 4999};
อินพุต:
long min_active = 5000;
string[] operations = new string[] {"average", "best", "add 5000", "add 4999", "active", "average"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {0, 0, 1, 4999};
คำอธิบาย
เมื่อยังไม่มีวันใดเลย คำถามทั้งสองได้ 0 ส่วน 5000 นับเป็นวันที่แอ็กทีฟ แต่ 4999 ไม่นับ และ (5000 + 4999) / 2 ปัดลงเป็น 4999
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
เก็บค่าที่อัปเดตไปเรื่อย ๆ (ผลรวม จำนวนวัน จำนวนวันที่แอ็กทีฟ และค่าสูงสุด) แทนการไล่ลิสต์ใหม่ทุกครั้ง
คำใบ้ 2
วันหนึ่งจะแอ็กทีฟเมื่อจำนวนก้าวมากกว่าหรือเท่ากับเป้าหมาย
คำใบ้ 3
ตรวจกรณีที่ยังไม่มีวันใดเลยก่อนจะหาร
ความซับซ้อนที่คาดหวัง
เวลา O(q), หน่วยความจำเพิ่ม O(1)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน