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

  의 크기

• 배열 정렬 a

• x :=1

• x

  • x를 1만큼 증가

• x가 n과 같으면

  • {0,0}

    쌍을 반환

• 최소값 :=0, j :=1

• i를 초기화하기 위해 :=0, i

  • curr :=a[i], lastPossible =a[i]

  • lastPossible> a[n - 1]이면 루프에서 나오십시오.

  • spaceInBetween :=거짓

  • j <=i이면,

    • j :=i + 1

  • 동안 j

    • a[j] - a[j - 1])> 1이면

      • spaceInBetween :=참

    • a[j] - a[j - 1])> 1이면

    • j를 1 증가

  • idx :=j - 1

  • n - (idx - i + 1)> 1이면

    • spaceInBetween :=참

• ballLeft :=i, ballRight :=n - (idx + 1)

• minVal :=ballLeft + ballRight + (spaceInBetween이 참이면 0, 그렇지 않으면 1)

• ans[0] :=minVal의 최소값 ans[0]

• ans[1] :=a[n - 2] - a[0] 및 a[n - 1] - a[1]) - (n - 2)의 최대값,

• 반환

• 메인 메소드 호출에서 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, ]