Ta hình dung các ngôi nhà là các cột đứng, khi này ta giả sử một đường ngang là đường tiêu chuẩn mà ta phải tháo dỡ hoặc xây thêm để tất cả ngôi nhà có cùng độ cao tiêu chuẩn ấy. Ta thấy rằng nếu ta tăng chiều cao của đường tiêu chuẩn lên, giá trị sẽ bé đi và khi đạt một giá trị nào đó nó sẽ tăng lên. Từ đó ta biết các giá trị của đường tiêu chuẩn khi tăng lên sẽ cho ra các giá trị tạo thành một parabol ~f(i)~ với ~f~ là hàm tính chi phí cần cho việc biến các tòa nhà bằng độ cao tiêu chuẩn ~i~ và ~i~ là độ cao tiêu chuẩn. Từ đây ta có thể dễ dàng tìm điểm min của parabol này với tìm kiếm tam phân .

Lưu ý: ~F(3)~ trong gif là ~2 \cdot 10 + 1 \cdot 100 + 0 \cdot 1000 = 120~

Code tham khảo của lds

long long cal(int x)
{
    long long ans=0;
    FOR(i,1,n)
        ans+=abs(a[i]-x)*b[i];
    return ans;
}

void lds_go_goooo()
{
    int l=1,r=1e4;
    while(r-l>4)
    {
        int m1=(l+r)/2;
        int m2=m1+1;
        if(cal(m1)>cal(m2)) l=m1;
        else    r=m1;
    }
    long long ans=1e12;
    FOR(i,l,r)
        ans=min(ans,cal(i));
    cout<<ans;
}

Giải thích code trên: Mình vẫn dùng như tìm kiếm nhị phân nhưng vì parabol không đồng biến nên ta cần một biến mid2 để kiểm tra xem mid1 ta đang ở phía nào của parabol và từ đó giới hạn ~l~ và ~r~.