Ta nhận xét mỗi lần gộp bi là mỗi lần đổi dấu của phần tử bên phải:

• Với các vị trí ~i~ có ~a_i < 0~, ta luôn muốn đổi dấu của đống này sau lần gộp cuối, do đó ta chỉ việc gộp thẳng đống này vào đống ~1~. Nhận được giá trị ~-a_i~.
• Với các vị trí ~i~ có ~a_i \geq 0~, ta sẽ có gắng giữ dấu của đống này sau lần gộp cuối, do đó ta sẽ gộp nó vào đống có dấu trừ gần nhất bên trái (lúc này đống này sẽ mang dấu trừ, sau bước gộp với đống ~1~ sẽ mang lại dấu cộng). Nhận được giá trị ~a_i~. Đống thứ ~2~ luôn mang dấu trừ, do đó ta luôn tồn tại đống gần nhất có dấu trừ bên trái.

Độ phức tạp: ~O(n)~.

Code tham khảo:

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 5), sign(n + 5, 0);
    for(int i = 1; i <= n; i++) cin >> a[i];
    long long ans = a[1] - a[2];
    for(int i = 3; i <= n; i++) ans += abs(a[i]);
    cout << ans;
}