C++で庭に水をやるために開く蛇口の最小数

庭全体に水を供給するために開く必要のある蛇口の最小数を見つける必要があります。可能な解決策がない場合は、-1を返します。

したがって、入力がn =5で、範囲が[3,4,1,1,1,0]の場合、出力は1になります。これは、2番目のタップから、地面全体をカバーするためです[-3 〜5]。

これを解決するには、次の手順に従います-

• これを解決するには、次の手順に従います-

• サイズ（n + 1）の配列vを定義し、これに-1を入力します

• 初期化i：=0の場合、i <=nの場合、更新（iを1増やします）、実行-

  • u：=最大i-範囲[i]および0

  • e：=最小nおよびi+範囲[i]

  • v [u]：=v[u]とeの最大値

• v [0]が-1と同じ場合、-

  • -1を返す

• curr：=v [0]

• i：=0、次：=0

• curr

  • i <=curr、do −

    • next：=nextとv[i]

      の最大値

    • （iを1増やします）

  • nextがcurrと同じ場合、-

    • -1を返す

  • curr：=next

  • （retを1増やします）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minTaps(int n, vector<int>& ranges) {
      int ret = 1;
      vector<int> v(n + 1, -1);
      for (int i = 0; i <= n; i++) {
         int u = max(i - ranges[i], 0);
         int e = min(n, i + ranges[i]);
         v[u] = max(v[u], e);
      }
      if (v[0] == -1)
      return -1;
      int curr = v[0];
      int i = 0;
      int next = 0;
      while (curr < n) {
         while (i <= curr) {
            next = max(next, v[i]);
            i++;
         }
         if (next == curr)
         return -1;
         curr = next;
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,4,1,1,1,0};
   cout << (ob.minTaps(5, v));
}

入力

5, {3,4,1,1,1,0}

出力

1