LOL 세계에 Teemo라는 영웅이 있고 그의 공격으로 인해 적 Ashe가 중독 상태가 될 수 있다고 가정합니다. 이제 Ashe를 향한 Teemo의 공격 오름차순 시계열과 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의 크기
- 0 ~ n – 1 범위의 i에 대해
- 시작:=t[i], 끝:=t[i] + d – 1
- currEnd <시작인 경우 ret :=ret + end – 시작 + 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