用C ++移动石头直到连续II

假设我们正在考虑一个无限数线，则第i个石头的位置由数组石头给出，而结石[i]表示第i个石头的位置。如果石头的位置最小或最大，则它是终点石头。现在，在每个回合中，我们拾起终点石并将其移至空位，以使其不再是终点石。

如果结石在说，结石= [1,2,5]，则我们无法将终点结石移动到位置5，因为将其移动到任何位置（例如0或3）仍将其作为终点结石。

当我们无法再移动时，该游戏将停止。因此，宝石处于连续位置。

在这里我们必须找到游戏何时结束，那么我们本可以进行的最小和最大移动次数是多少？成对找到答案[min_moves，max_moves]

例如，如果输入类似于[7,3,9]，则结果将为[1,3]

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为2的数组

• ans [0]：= inf，ans [1]：= -inf和n：= a的大小

• 对数组进行排序

• x：= 1

• 而x <n且a [x]＆a [x − 1]与1相同，则-

• x增加1

• 如果x与n相同，则

• 返回一对{0,0}

• minVal：= 0，j：= 1

• 用于初始化i：= 0，当i <a.size（时，将i增加1做-

• spaceInBetween：= true

• 如果a [j]-a [j-1]）> 1，则，

• 如果a [j]-a [j-1]）> 1，则，

• 将j增加1

• spaceInBetween：= true

• j：= i + 1

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

• 如果lastPossible> a [n-1]，则从循环中出来

• spaceInBetween：=假

• 如果j <= i，那么，

• 当j <n和a [j] <= lastPossible时，执行以下操作：

• idx：= j-1

• 如果n-（idx-i + 1）> 1，则，

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

• minVal：= ballLeft + ballRight +（当spaceInBetween为true时为0，否则为1）

• ans [0]：= minVal ans ans [0]的最小值

• ans [1]：= a [n-2]-a [0]和a [n-1]-a [1]）-(n-2)的最大值，

• 返回ans

• 从主要方法调用solve（石头）

示例

#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, ]