C++で連続IIまで石を動かす

無限の数直線を考えているとしましょう。ここでは、i番目の石の位置は配列石で与えられ、stones[i]はi番目の石の位置を示しています。石は、最小または最大の位置にある場合、終点の石です。今度は各ターンで、エンドポイントストーンを拾い上げ、それを空いている位置に移動して、エンドポイントストーンではなくなるようにします。

ストーンがたとえばstones=[1,2,5]の場合、エンドポイントストーンを任意の位置（0や3など）に移動してもエンドポイントストーンとして保持されるため、エンドポイントストーンを位置5に移動することはできません。 。

これ以上動かなくなると、このゲームは停止します。したがって、石は連続した位置にあります。

ここでは、ゲームがいつ終了するかを確認する必要があります。それでは、実行できた可能性のある移動の最小数と最大数はいくつになるでしょうか。ペアとして答えを見つける[min_moves、max_moves]

たとえば、入力が[7,3,9]の場合、結果は[1,3]

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

• サイズ2の配列を定義します

• ans [0]：=inf、ans [1]：=−infおよびn：=aのサイズ

• 配列を並べ替える

• x：=1

• x

  • xを1増やします

• xがnと同じ場合、

  • ペアを返す{0,0}

• minVal：=0、j：=1

• iを初期化する場合：=0、i

  • curr：=a [i]、lastPossible =a [i]

  • lastPossible> a [n --1]の場合、ループから出てきます

  • spaceInBetween：=false

  • j <=iの場合、

    • j：=i + 1

  • j

    • a [j]-a [j-1]）> 1の場合、

      • spaceInBetween：=true

    • a [j]-a [j-1]）> 1の場合、

    • jを1増やします

  • idx：=j-1

  • n-（idx --i + 1）> 1の場合、

    • spaceInBetween：=true

• ballLeft：=i、ballRight：=n-（idx + 1）

• minVal：=ballLeft + ballRight +（spaceInBetweenがtrueの場合は0、それ以外の場合は1）

• ans [0]：=minValの最小値ansans [0]

• ans [1]：=最大a[n-2]-a[0]およびa[n-1]-a[1]）-（n-2）、

• ansを返す

• メインメソッド呼び出しからsolve（stones）

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> solve(vector<int> a) {
      vector <int> ans(2);
      ans[0] = INT_MAX;
      ans[1] = INT_MIN;
      int n = a.size();
      sort(a.begin(), a.end());
      int x = 1;
      while(x < n && a[x] - a[x - 1] == 1)
         x ++;
      if(x == n){
         return {0,0};
      }
      int minVal = 0;
      int j = 1;
      for(int i = 0; i < a.size(); i++){
         int curr = a[i];
         int lastPossible = a[i] + n - 1;
         if(lastPossible > a[n - 1])
            break;
         bool spaceInBetween = false;
         if(j <= i)
            j = i + 1;
            while(j < n && a[j] <= lastPossible){
               if((a[j] - a[j - 1]) > 1) {
                  spaceInBetween = true;
               }
               j++;
            }
           int idx = j - 1;
           if(n - (idx - i + 1) > 1)
              spaceInBetween = true;
           int ballLeft = i;
           int ballRight = n - (idx + 1);
           minVal = ballLeft + ballRight + (spaceInBetween? 0 : 1);
           ans[0] = min(minVal, ans[0]);
        }
       ans[1] = max(a[n - 2] - a[0], a[n - 1] - a[1]) - (n -2);
       return ans;
   }
   vector<int> numMovesStonesII(vector<int>& stones) {
      return solve(stones);
   }
};
main(){
   Solution ob;
   vector<int> v1 = {7,3,9};
   print_vector(ob.numMovesStonesII(v1));
}

入力

[7,3,9]

出力

[1, 3, ]