สมมติว่าเราพิจารณาเส้นจำนวนแบบอนันต์ ตำแหน่งของหินที่ i กำหนดโดยอาร์เรย์ stones และ stones[i] แสดงตำแหน่งของหินที่ i หินเป็นหินปลายถ้ามีตำแหน่งน้อยที่สุดหรือมากที่สุด ตอนนี้ในแต่ละเทิร์น เราเลือกหินปลายหนึ่งและย้ายไปตำแหน่งว่างเพื่อให้มันไม่ใช่หินปลายอีกต่อไป
ถ้าหินอยู่ที่ stones = [1,2,5] เราไม่สามารถย้ายหินปลายที่ตำแหน่ง 5 ได้ เพราะการย้ายไปตำแหน่งไหน (เช่น 0 หรือ 3) จะทำให้หินนั้นยังคงเป็นหินปลายอยู่
เกมนี้จะหยุดเมื่อเราไม่สามารถเคลื่อนไหวได้อีก กล่าวคือ หินอยู่ในตำแหน่งที่เรียงติดกัน
เราต้องหาเมื่อเกมจบ จำนวนการเคลื่อนไหวขั้นต่ำและสูงสุดที่เราอาจทำได้ คือ หาคำตอบเป็นคู่ [min_moves, max_moves]
เช่น ถ้าอินพุตเป็น [7,3,9] ผลลัพธ์จะเป็น [1,3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
กำหนดอาร์เรย์ ans ขนาด 2
ans[0] := inf, ans[1] := -inf และ n := ขนาดของ a
เรียงอาร์เรย์ a
x := 1
ทำซ้ำ while x < n และ a[x] - a[x-1] เท่ากับ 1 ให้เพิ่ม x ขึ้น 1
ถ้า x เท่ากับ n ให้คืนค่า {0,0}
minVal := 0, j := 1
ลูป i จาก 0 ถึง a.size()-1:
curr := a[i], lastPossible = a[i] + n - 1
ถ้า lastPossible > a[n-1] ให้ออกจากลูป
spaceInBetween := false
ถ้า j <= i ให้ j := i + 1
ทำซ้ำ while j < n และ a[j] <= lastPossible:
ถ้า (a[j] - a[j-1]) > 1 ให้ spaceInBetween := true
เพิ่ม j ขึ้น 1
idx := j - 1
ถ้า n - (idx - i + 1) > 1 ให้ spaceInBetween := true
ballLeft := i, ballRight := n - (idx + 1)
minVal := ballLeft + ballRight + (0 ถ้า spaceInBetween จริง มิฉะนั้น 1)
ans[0] := min ของ minVal และ ans[0]
ans[1] := max ของ (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, ]
