Tấn công Teemo (Teemo Attacking) trong C++

Teemo tấn công tại các thời điểm trong mảng t (tăng dần). Mỗi tấn công gây độc trong d giây. Tính tổng thời gian bị độc (gộp các khoảng chồng lấn).

Ví dụ: t=[1,4], d=2 → độc [1,2] và [4,5] → tổng 4 giây.

Thuật toán (Gộp khoảng)

1. Duyệt các thời điểm tấn công.
2. Khoảng độc hiện tại: [start, end] với start=t[i], end=t[i]+d-1.
3. Nếu start > currEnd → cộng end-start+1, cập nhật currEnd=end.
4. Ngược lại → cộng end-currEnd (phần mở rộng), cập nhật currEnd=end.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findPoisonedDuration(vector& t, int d) {
        int ret=0, currEnd=-1;
        for (int start : t) {
            int end = start + d - 1;
            if (currEnd < start) {
                ret += end - start + 1;
                currEnd = end;
            } else {
                ret += end - currEnd;
                currEnd = end;
            }
        }
        return ret;
    }
};

int main() {
    vector v = {1,4};
    Solution ob;
    cout << ob.findPoisonedDuration(v, 2); // 4
    return 0;
}

Đầu vào / Đầu ra

Input: [1,4] 2

Output: 4