Hiểu bài toán

Cho hai số nguyên L và R (-10^9 ≤ L < R ≤ 10^9). Tìm một số nguyên M trong đoạn [L, R] sao cho hiệu số giữa tổng các số từ L đến M và tổng các số từ M+1 đến R là nhỏ nhất (tuyệt đối). Nói cách khác, cần tìm M使得 |sum(L..M) - sum(M+1..R)| minimized.

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

Cách Phương pháp tìm M tối ưu theo công thức

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    ll L, R;
    cin >> L >> R;
    // From 2(M+1) = L + R + 1 => M = (L+R-1)/2
    ll M = (L + R - 1) / 2;
    cout << M << endl;
    return 0;
}

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

Đề bài yêu cầu tìm M使得 |Sum(L..M) - Sum(M+1..R)| min. Ta có tổng từ L đến M là (M-L+1)(L+M)/2 và từ M+1 đến R là (R-M)(M+1+R)/2. Để hiệu số này nhỏ nhất về mặt tuyệt đối, ta cần chia dãy số thành 2 phần có tổng xấp xỉ bằng nhau. Nếu ta coi dãy số là một tổng thể, tổng toàn bộ là (L+R)(R-L+1)/2. Khi đó ta cần tìm M使得 Sum(L..M) ≈ Sum(M+1..R). Điều này tương đương với 2(M+1) ≈ L + R + 1. Do M phải là số nguyên, ta suy ra M = floor((L + R - 1) / 2). Đây là đáp án chính xác cho hầu hết các trường hợp.

Cách Tối ưu hóa Binary Search

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;

ll sum(ll a, ll b) {
    return (b - a + 1) * (a + b) / 2;
}

int main() {
    ll L, R;
    cin >> L >> R;

    ll left = L, right = R;
    ll best_m = L;
    ll min_diff = -1;

    while (left <= right) {
        ll mid = left + (right - left) / 2;

        // Calculate difference for mid
        ll s1 = sum(L, mid);
        ll s2 = sum(mid + 1, R);
        ll diff_mid = abs(s1 - s2);

        // Check neighbors to ensure minimum
        ll diff_prev = (mid > L) ? abs(sum(L, mid-1) - sum(mid, R)) : -1;
        ll diff_next = (mid < R) ? abs(sum(L, mid+1) - sum(mid+2, R)) : -1;

        if (min_diff == -1 || diff_mid < min_diff) {
            min_diff = diff_mid;
            best_m = mid;
        }

        // Determine direction based on where the function is decreasing
        if (mid > L && diff_prev < diff_mid) {
            right = mid - 1;
        } else if (mid < R && diff_next < diff_mid) {
            left = mid + 1;
        } else {
            break;
        }
    }
    cout << best_m << endl;
    return 0;
}

• Time Complexity: O(log(R-L))
• Space Complexity: O(1)

Sử dụng Binary Search để tìm điểm mà tại đó hiệu số tổng hai bên đạt minimum. Hàm f(M) = |Sum(L..M) - Sum(M+1..R)| có dạng 'hình chữ U' (giảm đến điểm tối ưu rồi tăng lên). Ta có thể dùng binary search để tìm điểm này. Tuy nhiên, do hàm số nguyên và có độ dốc không đều, việc xác định hướng tìm kiếm cần kiểm tra các giá trị lân cận (mid-1, mid, mid+1). Nếu diff giảm về phía bên trái (diffprev < diffmid), ta tìm tiếp bên trái. Ngược lại, nếu diffnext < diffmid, ta tìm bên phải. Nếu không có điểm nào thấp hơn mid, mid chính là điểm tối ưu.

Cách Duyệt nhị phân (Binary Search) đơn giản

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;

ll sum(ll a, ll b) {
    return (b - a + 1) * (a + b) / 2;
}

int main() {
    ll L, R;
    cin >> L >> R;

    ll low = L, high = R;
    ll ans = L;

    while (low <= high) {
        ll mid = low + (high - low) / 2;
        // Tính chênh lệch tại mid
        ll s_left = sum(L, mid);
        ll s_right = sum(mid + 1, R);
        ll diff_mid = abs(s_left - s_right);

        // Tính chênh lệch tại mid + 1 (nếu hợp lệ)
        ll diff_next = 1e18;
        if (mid < R) {
            ll s_left_next = sum(L, mid + 1);
            ll s_right_next = sum(mid + 2, R);
            diff_next = abs(s_left_next - s_right_next);
        }

        // Nếu chênh lệch tại mid nhỏ hơn hoặc bằng mid+1, ta ưu tiên mid hoặc tìm bên trái
        // Thực chất ta đang tìm điểm bắt đầu tăng -> điểm tối ưu
        if (diff_mid <= diff_next) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(log(R-L))
• Space Complexity: O(1)

Đây là biến thể đơn giản hóa của Binary Search. Hàm số f(M) giảm đến một điểm rồi tăng lên. Ta cần tìm điểm đầu tiên mà tại đó giá trị bắt đầu tăng (hoặc giá trị tại đó nhỏ nhất). Trong vòng lặp, ta so sánh giá trị tại mid và mid + 1. Nếu f(mid) <= f(mid+1), điều này có nghĩa là điểm tối ưu nằm ở bên trái hoặc chính là mid. Do đó, ta lưu mid làm đáp án và thu hẹp khoảng tìm kiếm về bên trái (high = mid - 1). Ngược lại, nếu f(mid) > f(mid+1), điểm tối ưu đang nằm bên phải, ta tìm sang phải (low = mid + 1).

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

Bài học kinh nghiệm

• Bài toán có thể quy về phương trình toán học: M ≈ (L + R - 1) / 2.
• Hàm chênh lệch tổng theo M có dạng đơn điệu (giảm rồi tăng), cho phép áp dụng Binary Search.
• Lưu ý về số nguyên lớn (long long) và tràn số khi tính tổng, cần công thức cộng dồn số học an toàn.

Lỗi thường gặp

• Sử dụng biến int dẫn đến tràn số khi L, R lên tới 10^9.
• Lỗi logic trong Binary Search: không xác định đúng hướng tìm kiếm nếu chỉ so sánh giá trị đơn thuần mà không xét biến thiên đạo hàm.
• Xử lý sai trường hợp biên (ví dụ M = L hoặc M = R).