Hiểu bài toán

Bài toán yêu cầu tìm số lần biến đổi tối thiểu để làm cho tất cả các phần tử trong dãy số bằng nhau. Quy tắc biến đổi là mỗi lần chỉ được tăng N-1 phần tử lên 1 đơn vị. Nhìn thoáng qua có vẻ như ta cần tăng các số nhỏ lên, nhưng thực chất ta có thể coi thao tác này tương đương với việc giảm 1 phần tử bất kỳ xuống 1 đơn vị (vì mục tiêu là sự bằng nhau, việc tăng tất cả trừ một phần tử cũng giống như việc giữ nguyên các phần tử khác và giảm phần tử đó đi 1). Với cách nhìn này, để đưa tất cả các phần tử về cùng một giá trị, ta cần giảm từng phần tử về giá trị nhỏ nhất của dãy. Do đó, số lần biến đổi bằng tổng chênh lệch giữa các phần tử và giá trị nhỏ nhất.

Các cách tiếp cận

Cách Giả lập tương đương (Logic)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Tìm giá trị nhỏ nhất
    long long min_val = *min_element(a.begin(), a.end());

    // Tính tổng chênh lệch của tất cả các phần tử so với giá trị nhỏ nhất
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (a[i] - min_val);
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan nhất dựa trên việc quan sát quy tắc biến đổi. Mỗi lần biến đổi tăng N-1 phần tử lên 1, về mặt toán học tương đương với việc giữ nguyên 1 phần tử và giảm N-1 phần tử còn lại đi 1. Để biến đổi cả dãy số về cùng một giá trị, ta cần giảm các phần tử lớn hơn về giá trị nhỏ nhất (min) của dãy. Vì vậy, số lần biến đổi cần thiết bằng tổng của tất cả các hiệu a[i] - min_val. Ta dùng hàm min_element để tìm giá trị nhỏ nhất và accumulate hoặc vòng lặp để tính t tổng chênh lệch.

Cách Tối ưu tính toán

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Sử dụng hàm có sẵn để tìm min và tính tổng
    int minn = *min_element(a.begin(), a.end());
    long long tong = accumulate(a.begin(), a.end(), 0LL);

    // Công thức: tổng chênh lệch = tổng các số - (số lượng * số nhỏ nhất)
    long long ans = tong - (long long)minn * n;

    cout << ans;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là phiên bản tối ưu hóa của cách tiếp cận đầu tiên. Thay vì lặp qua mảng một lần nữa để tính tổng chênh lệch, ta có thể tính toán trực tiếp dựa trên tổng giá trị các phần tử và giá trị nhỏ nhất. Số lần biến đổi = (Tổng các phần tử) - (Giá trị nhỏ nhất * N). Cách này giúp mã nguồn ngắn gọn hơn và tận dụng các hàm chuẩn của C++ (accumulate với kiểu dữ liệu long long để tránh tràn số).

Cách Xử lý dữ liệu trực tiếp (Stream)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long tong = 0;
    int mn = INT_MAX;

    // Đọc và xử lý dữ liệu ngay khi nhập để tiết kiệm bộ nhớ
    for(int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        tong += temp;
        mn = min(temp, mn);
    }

    cout << tong - (long long)mn * n;

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Cách tiếp cận này tối ưu về bộ nhớ. Thay vì lưu toàn bộ dãy số vào một vector, ta chỉ cần duy nhất một biến để lưu giá trị nhỏ nhất (mn) và một biến để lưu tổng (tong). Khi đọc từng số, ta cập nhật ngay lập tức hai giá trị này. Điều này giúp giảm bộ nhớ sử dụng đáng kể, phù hợp với các bài toán có giới hạn bộ nhớ nghiêm ngặt (mặc dù với N=10^5, cách dùng vector vẫn chấp nhận được).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Quy tắc 'tăng N-1 phần tử' tương đương với 'giảm 1 phần tử' về mặt mục tiêu làm cho các phần tử bằng nhau. Do đó, ta chỉ cần đưa tất cả về giá trị nhỏ nhất của dãy.
• Số lần biến đổi không phụ thuộc vào giá trị đích cuối cùng (miễn là >= min), mà chỉ phụ thuộc vào chênh lệch giữa các phần tử và giá trị nhỏ nhất.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu tính tổng theo kiểu int mà A_i lên tới 10^9 và N=10^5, tổng có thể lên tới 10^14, vượt quá giới hạn của int. Cần dùng long long cho biến tổng.
• Sai logic khi chọn giá trị đích: Một số người nghĩ cần đưa các số về giá trị trung bình hoặc giá trị bất kỳ, nhưng thực tế chỉ cần đưa về giá trị nhỏ nhất là tối ưu nhất.