ย้ายหินจนกว่าจะติดต่อกัน II ใน C ++

สมมติว่าเรากำลังพิจารณาเส้นจำนวนอนันต์ ที่นี่ตำแหน่งของหินที่ i ถูกกำหนดโดยหินอาร์เรย์ และหิน[i] แสดงถึงตำแหน่งของหิน หินเป็นหินปลายทางหากมีตำแหน่งที่เล็กที่สุดหรือใหญ่ที่สุด ในแต่ละเทิร์น เราหยิบหินเอ็นด์พอยท์และย้ายไปยังตำแหน่งที่ว่างเพื่อไม่ให้เป็นหินเอ็นด์พอยท์อีกต่อไป

หากหินอยู่ที่ตำแหน่ง กล่าวคือ หิน =[1,2,5] เราไม่สามารถย้ายหินจุดสิ้นสุดที่ตำแหน่ง 5 ได้ เนื่องจากการย้ายไปยังตำแหน่งใดๆ (เช่น 0 หรือ 3) จะยังคงเก็บหินนั้นเป็นหินปลายทาง .

เกมนี้จะหยุดเมื่อเราไม่สามารถเคลื่อนไหวได้อีกต่อไป ดังนั้นหินจึงอยู่ในตำแหน่งที่ต่อเนื่องกัน

ที่นี่เราต้องค้นหาเมื่อเกมจบลง ดังนั้นจำนวนการเคลื่อนไหวขั้นต่ำและสูงสุดที่เราสามารถทำได้คืออะไร? หาคำตอบเป็นคู่ [min_moves, max_moves]

ตัวอย่างเช่น หากอินพุตเป็น [7,3,9] ผลลัพธ์จะเป็น [1,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ขนาด 2

• ans[0] :=inf, ans[1] :=−inf and n :=size of a

• จัดเรียงอาร์เรย์ 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 :=เท็จ

  • ถ้า j <=i แล้ว

    • เจ :=ผม + 1

  • ในขณะที่ j

    • ถ้า a[j] - a[j - 1])> 1 แล้ว

      • spaceInBetween :=จริง

    • ถ้า a[j] - a[j - 1])> 1 แล้ว

    • เพิ่มขึ้น 1

  • idx :=j - 1

  • ถ้า n - (idx - i + 1)> 1 แล้ว

    • spaceInBetween :=จริง

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

• minVal :=ballLeft + ballRight + (0 เมื่อ spaceInBetween เป็นจริง มิฉะนั้น 1)

• ans[0] :=ขั้นต่ำของ minVal ans[0]

• ans[1] :=สูงสุดของ a[n - 2] - a[0] และ a[n - 1] - a[1]) - (n - 2),

• กลับมาอีกครั้ง

• จากเมธอดหลัก เรียก แก้(หิน)

ตัวอย่าง

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