สมมุติว่าในโลก LOL มีฮีโร่ชื่อ Teemo และการโจมตีของเขาสามารถทำให้ Ashe ศัตรูของเขาติดพิษได้ สมมติว่าเราได้ให้อนุกรมเวลาที่โจมตีของ Teemo จากน้อยไปมากไปหา Ashe และระยะเวลาการเป็นพิษต่อการโจมตีของ Teemo เราต้องหาเวลาทั้งหมดที่ Ashe อยู่ในสภาพเป็นพิษ เราสามารถสรุปได้ว่า Teemo โจมตีที่จุดเริ่มต้นของจุดเวลาที่กำหนด และทำให้ Ashe อยู่ในสภาพที่เป็นพิษทันที
อินพุตเป็นเหมือน [1,4] และ 2 จากนั้นผลลัพธ์จะเป็น 4 นี่เป็นเพราะ ณ จุดที่ 1 Teemo เริ่มโจมตี Ashe และทำให้ Ashe ถูกวางยาพิษทันที สถานะพิษนี้จะคงอยู่ 2 วินาทีจนถึงจุดสิ้นสุดของเวลาที่ 2 และ ณ จุดที่ 4 Teemo จะโจมตีศัตรูนี้อีกครั้ง และทำให้ Ashe อยู่ในสถานะเป็นพิษเป็นเวลา 2 วินาที ในที่สุดคุณต้องส่งออก 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตั้งค่า ret :=0
- currEnd :=-1
- n :=ขนาดของ t
- สำหรับ i ในช่วง 0 ถึง n – 1
- เริ่มต้น :=t[i], สิ้นสุด :=t[i] + d – 1
- ถ้า currEnd
- มิฉะนั้น ret :=ret + end – currEnd, currEnd :=end
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findPoisonedDuration(vector<int>& t, int d) {
int ret = 0;
int currEnd = -1;
int n = t.size();
for(int i = 0; i < n; i++){
int start = t[i];
int end = t[i] + d - 1;
if(currEnd < start){
ret += end - start + 1;
currEnd = end;
} else {
ret += end - currEnd;
currEnd = end;
}
}
return ret;
}
};
main(){
vector<int> v = {1,4};
Solution ob;
cout << (ob.findPoisonedDuration(v, 2));
} อินพุต
[1,4] 4
ผลลัพธ์
4
