Участник:Никита Плетнев/minimum number of taps

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/submissions/

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        for (int i = 0; i < ranges.size(); ++i) {
            if (ranges[i] == 0)
                ranges[i] = i;
            else {
                int range = 0;
                if (ranges[i] < i)
                    range = i - ranges[i];
                if (i + ranges[i] > ranges[range])
                    ranges[range] = i + ranges[i];
            }
        }
        int idx_max = 0, position = 0, reswitch = 0;
        for (int i = 0; i < n; ++i){
            if (i > idx_max) 
                return -1;
            if (ranges[i] > idx_max)
                idx_max = ranges[i];
            if (i == position) {
                ++reswitch;
                position = idx_max;
            }
        }
        if (idx_max >= n)
            return reswitch;
        else
            return -1;
    }
};