Minimum Increment to Make Array Unique ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A การเคลื่อนไหว 1 ครั้ง = เพิ่มค่า A[i] ขึ้น 1 ต้องการจำนวนการเคลื่อนไหวน้อยที่สุดเพื่อให้ค่าทั้งหมดไม่ซ้ำกัน

ตัวอย่าง: [3,2,1,2,1,7] → 6 (กลายเป็น [3,4,1,2,5,7] หรือแบบอื่นที่ไม่ซ้ำ)

วิธีแก้ปัญหา (Sort + Greedy)

1. เรียงอาร์เรย์จากน้อยไปมาก
2. วนจากซ้ายไปขวา: ถ้า A[i] <= A[i-1] ต้องเพิ่มให้เป็น A[i-1] + 1
3. สะสมจำนวนที่เพิ่ม

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        sort(A.begin(), A.end());
        int moves = 0;
        for(int i = 1; i < A.size(); i++) {
            if(A[i] <= A[i-1]) {
                moves += (A[i-1] + 1) - A[i];
                A[i] = A[i-1] + 1;
            }
        }
        return moves;
    }
};

int main() {
    vector<int> v1 = {3,2,1,2,1,7};
    Solution ob;
    cout << ob.minIncrementForUnique(v1);
    return 0;
}

อินพุต

[3,2,1,2,1,7]

เอาต์พุต

6