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