Di chuyển đá cho đến khi liên tiếp II trong C++

Giới thiệu

Cho mảng stones là vị trí các viên đá trên đường thẳng vô hạn. Viên đá đầu/cuối (endpoint) là viên có vị trí nhỏ nhất/lớn nhất. Mỗi lượt, chọn một endpoint stone và di chuyển đến vị trí trống sao cho nó không còn là endpoint. Trò chơi dừng khi các viên đá nằm ở các vị trí liên tiếp. Tìm số lượt di chuyển tối thiểu và tối đa.

Ví dụ

Đầu vào: [7,3,9] → Đầu ra: [1,3]

Ý tưởng giải thuật

Số lượt tối đa (max_moves)

Di chuyển endpoint stone từng bước một về phía trung tâm. Công thức:

max_moves = max(stones[n-2] - stones[0], stones[n-1] - stones[1]) - (n - 2)

Số lượt tối thiểu (min_moves)

Sử dụng cửa sổ trượt (sliding window) để tìm đoạn dài n chứa nhiều đá nhất:

1. Sắp xếp mảng.
2. Với mỗi i, tìm j lớn nhất sao cho stones[j] - stones[i] + 1 <= n (độ dài cửa sổ ≤ n).
3. Số đá trong cửa sổ = j - i + 1, số đá ngoài = n - (j - i + 1).
4. Trường hợp đặc biệt: nếu n - (j - i + 1) == 1 và cửa sổ gần như đầy (chỉ thiếu 1 vị trí ở giữa) → cần 2 lượt (ví dụ: [1,2,3,4,6] với n=5).
5. Cập nhật min_moves = min(min_moves, đá_ngoài + (đặc_biệt ? 1 : 0)).

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        
        // Kiểm tra đã liên tiếp
        bool consecutive = true;
        for (int i = 1; i < n; i++) {
            if (stones[i] - stones[i-1] != 1) { consecutive = false; break; }
        }
        if (consecutive) return {0, 0};
        
        // Max moves
        int maxMoves = max(stones[n-2] - stones[0], stones[n-1] - stones[1]) - (n - 2);
        
        // Min moves - sliding window
        int minMoves = n;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j + 1 < n && stones[j+1] - stones[i] + 1 <= n) j++;
            int inWindow = j - i + 1;
            int outside = n - inWindow;
            if (outside == 1 && inWindow == n - 1 && stones[j] - stones[i] + 1 == n - 1)
                minMoves = min(minMoves, 2);
            else
                minMoves = min(minMoves, outside);
        }
        
        return {minMoves, maxMoves};
    }
};

int main() {
    Solution ob;
    vector<int> v = {7, 3, 9};
    auto ans = ob.numMovesStonesII(v);
    cout << "[" << ans[0] << ", " << ans[1] << "]";
    return 0;
}

Đầu vào

[7,3,9]

Đầu ra

[1, 3]