Tìm chiều cao chung của các tòa nhà với chi phí tối thiểu

Question

Đây là câu hỏi từ một số cuộc thi lập trình (tôi không biết chính xác cuộc thi lập trình nào thuộc về, tôi đã xem nó một năm trước). Câu hỏi đặt ra là như sau:

Có N tòa nhà, từng có chiều cao của nó riêng (không nhất thiết phải độc đáo)

{h1,h2,h3,...,hn} 

Chúng ta phải làm cho tất cả các tòa nhà của cùng một chiều cao nói h.

Các hoạt động cho phép là:

1. Chúng ta có thể thêm một số chiều cao một tòa nhà.
2. Chúng tôi có thể xóa một số chiều cao khỏi tòa nhà.

Có chi phí liên quan đến mỗi tòa nhà để xóa/thêm chiều cao đơn vị. Nói c (i) là chi phí để loại bỏ/thêm chiều cao đơn vị vào một tòa nhà. Chi phí tương ứng như sau:

{c1,c2,c3,...,cn} 

Giả sử chúng tôi có đủ chiều cao (đơn vị), chúng tôi phải tìm chi phí tối thiểu để làm cho tất cả các tòa nhà có cùng độ cao.

Nhập: Dòng đầu tiên sẽ chỉ định N số lượng tòa nhà. (1 < = N < = 100000). Dòng thứ hai của đầu vào sẽ dành cho chiều cao của tòa nhà.

{h1,h2,h3,...,hn} 

dòng thứ ba của đầu vào sẽ cung cấp cho các mảng chi phí

{c1,c2,c3.....,cn} 

Output

Sản lượng sẽ chỉ đơn giản là chi phí tối thiểu cần thiết.

Sample Input:

3 

2 1 3 

10 1000 1 

Sample Output

12 

Giải thích: Làm cho tất cả các tòa nhà có chiều cao 1, vì vậy chi phí sẽ 10 * (2-1) + 1000 * (1-1) + 1 * (3-1) tức là 12.

Tôi biết phương pháp lực lượng vũ phu là O (n^2).

Phương pháp brute force tôi nghĩ là như sau:

Dù chiều cao h chung được, nó phải là từ

{h1,h2,h3,....,hn} 

ví dụ: h phải bằng bất kỳ h (i). Bây giờ kiểm tra từng h (i) tôi có thể tính toán câu trả lời trong O (n^2).

có thể thực hiện nhanh hơn không?

Answer 1

O (n log (n)) Giải pháp:

Lết h (i) biểu thị chiều cao của tòa nhà thứ i và để c (i) biểu thị chi phí của tòa nhà thứ i.

1. Bước 1: Sắp xếp tòa nhà theo chiều cao của các tòa nhà tương ứng theo thứ tự giảm dần. Để sự sắp xếp này được gọi là P. P (1) là chiều cao của tòa nhà lớn nhất và P (n) là chiều cao của tòa nhà nhỏ nhất. Điều này có O (n log n).
2. Bước 2: Tổng tất cả chiều cao của tòa nhà. Cho S biểu thị tổng này. Bước này có thời gian O (n).
3. Bước 3: Hãy để Cost_of_Increase (i) biểu thị chi phí nếu chúng ta tạo chiều cao của tất cả các tòa nhà có chiều cao LESS so với tòa nhà thứ i bằng chiều cao của tòa nhà thứ i trong SORTED ARRAY P, tức là Cost_of_Increase (i) nếu chúng ta làm cho các tòa nhà P (i-1), P (i-2), ... P (n) bằng với chiều cao của tòa nhà P (i).

Bây giờ sử dụng đệ quy này:

Cost_of_Increase (i) = Cost_of_Increase (i-1) + (h (i) -h (i-1)) * (Sum chi phí của P (i- 1) tòa nhà thứ thành P (n) th builing)

Lưu ý rằng trong đệ quy trên, thứ tự của i và i-1 theo thứ tự của P, tức là thứ tự sắp xếp.

Bây giờ, hãy để Cost_of_decrease (i) biểu thị chi phí nếu chúng tôi làm cho tất cả các tòa nhà có chiều cao lớn hơn tòa nhà thứ i bằng chiều cao hte của tòa nhà thứ i trong SORTED ARRAY P, tức là Cost_of_decrease (i) nếu chúng tôi thực hiện các tòa nhà P (1), P (2), ... P (i-2), P (i-1) bằng với chiều cao của tòa nhà P (i).

Đối với sử dụng này đệ quy này:

Cost_of_decrease (i) = Cost_of_decrease (i + 1) + (h (i + 1) -h (i)) * (Sum chi phí của P (1) thứ xây dựng để P (i-1) lần thứ xây dựng)

vì vậy, tổng chi phí cho việc thực hiện chiều cao của tất cả các tòa nhà bằng P (i) ngày xây dựng là:

Cost_of_Increase (i) + Cost_of_decrease (i).

Khi chúng tôi có điều này cho tất cả các tòa nhà, chỉ cần kiểm tra xem chi phí nào nhỏ nhất và đó là câu trả lời.

Hy vọng điều đó sẽ hữu ích!

Answer 2

Thực hiện ternary search hoặc sử dụng thuật toán hill climbing về chiều cao của tất cả các tòa nhà sau khi kết thúc thuật toán. Đối với mỗi chiều cao, bạn có thể tính toán chi phí theo thời gian tuyến tính để độ phức tạp tổng thể sẽ là O (N * log (H)) trong đó H là chiều cao kết quả tối đa có thể.

EDIT: đây là một đoạn mã giả mà nên làm việc cho bạn (điều này được đồi leo giống như cách tiếp cận)

typedef long long ll; 
    ll get_cost(int h) { 
    if (h < 0 || h > MAX_HEIGHT) { 
     return MAX_VAL; // some unreachable positive value 
    } 
    ... 
    } 


    int main() { 
    ... 
    int current = 0; 
    int leftp, rightp; 
    ll cv, lv, rv; 
    ll step = SOME_BIG_ENOUGH_VALUE; 
    while (step > 0) { 
     leftp = current - step; 
     rightp = current + step; 
     cv = get_cost(current); 
     lv = get_cost(leftp); 
     rv = get_cost(rightp); 
     if (cv <= rv && cv <= lv) { 
     step /= 2; 
     } else if (lv < rv) { 
     current = leftp; 
     } else { 
     current = rightp; 
     } 
    } 
    ... 
    }