Tạo mảng chi phí ít nhất

Question

Tôi có một mảng có kích thước n + 1, nơi tôi muốn lưu trữ chi phí thấp nhất mua n mục (i^th chỉ số cửa hàng chi phí i^th mục).

Có m bán khác nhau: mỗi người bán cung cấp hàng L đến mục R (nơi L, R> = 1 và L, R < = n) với chi phí C mỗi.

Để tạo mảng chi phí ít nhất tôi đã làm như sau:

for (int i=1; i<=m; i++) { 
    int L = L of i^th seller 
    int R = R of i^th seller 
    int C = selling price of i^th seller 
    for (int j=L; j<=R; j++) { 
     if (leastCost[j]==0 || leastCost[j]>C) { 
      leastCost[j]=C 
    } 
} 

Xây dựng mảng này là O(n*m) và truy cập vào mảng này là O(1).

Đối với các giá trị rất lớn là n và m, có cách nào tốt hơn để tạo mảng chi phí thấp nhất không?

Có lẽ một cách tiếp cận khác không lưu trữ nó trong một mảng và một thứ gì khác để giảm độ phức tạp tổng thể?

Answer 1

Chắc chắn, chúng ta có thể làm tốt hơn O (n * m) và cũng là giải pháp rất đơn giản.

Tiếp theo là các mã giả để giải quyết vấn đề này:

Construct a MIN-HEAP of the sellers based on their costs c. 

Construct another array x[1...n] with its each element set to 0 initially. 

Do the following initializations: 
count=0 

while(count < n) 
{ 
S = EXTRACT_MIN(Heap) 
if(count==0) 
{    
    for(j=S.L to S.R) 
    { 
    leastCost[j]=S.c 
    ++count 
    x[j]=S.R 
    } 
} 
else 
{ 
    for(j=S.L;j<=S.R;++j) 
    { 
    if(x[j]!=0) 
    { 
    i=x[j] and continue; 
    } 
    else 
    { 
    leastCost[j]=S.c 
    ++count 
    x[j]=S.R 
    } 
    } 
} 
} 

Giải thích

Việc tối ưu hóa tốt nhất mà chúng ta có thể đạt được trong vấn đề này là chúng ta skip tất cả những chỉ số mảng mà đã đầy bởi vì họ đã có chi phí ít nhất.

x mảng helper: Mảng x giúp chúng ta bỏ qua tất cả các chỉ số mảng đó đã được lấp đầy bởi vì:

x [i] cửa hàng chỉ số j mà i tới j đã có chi phí ít nhất được điền vào mảng vì vậy đây là lý do để sử dụng câu lệnh có điều kiện:

if(x[i]!=0) 
{ 
i=x[i] and continue; 
} 

Vì vậy, về cơ bản nó giúp chúng tôi chuyển thẳng đến chỉ mục không được lấp đầy.

MIN-HEAP: Nó cho phép chúng tôi tìm chi phí tối thiểu c của tất cả các chi phí có trong thời gian O (nhật ký).

Thời gian phức tạp

Kể từ khi chúng tôi truy cập vào mảng leastCost nhiều nhất n lần do đó để truy cập vào các mảng: O (n)

Xây dựng đống mất O (m)

Trong trường hợp xấu nhất tất cả người bán sẽ đóng góp vào một số chỉ mục và sẽ có chính xác m hoạt động EXTRACT_MIN (Heap) và mỗi hoạt động mất O (logm) thời gian cho thời gian này là: O (m * logm).

Do đó tổng thời gian phức tạp = O (n + mlogm + m) = O (n + mlogm).

Nhân tiện, nếu tôi đang sử dụng ngôn ngữ C, tôi sẽ sử dụng cấu trúc cho Người bán và nếu Java sau đó là lớp dành cho Người bán. Hãy miễn phí cho mọi truy vấn.

Answer 2

Bạn có thể sử dụng một số hình thức ngăn xếp tại đây

Sắp xếp thứ nhất tất cả người bán bởi L. và bởi C desc nếu L bằng nhau.

Sau đó, bắt đầu từ người bán thứ nhất (với min Li)

Nếu ngăn xếp được để trống vào ngăn xếp. Nếu không có nhiều người bán với

(Lj == Li) 

sau đó cost[Li] = C[i] và Li++ (trong ngăn xếp)

nếu có nhập với Lj == Li sau đó

• nếu Rj < Ri và Cj > Ci skip

• nếu Rj < Ri và Cj < Ci thêm người bán này để ngăn xếp

• nếu Rj > Ri và Cj > Ci sau đó bật bán hiện tại (i), thêm người bán này (j) và thêm bán (i)

Answer 3

Vấn đề này là một vấn đề cổ điển Range minimum query, mà bạn có thể sử dụng Segment tree để có được một giải pháp có độ phức tạp thời gian O (m log n) để tạo cây và O (log n) cho mỗi truy vấn.

Chi tiết khác:

Chúng tôi sử dụng một cây để biểu thị giá tối thiểu cho mỗi mục từ 1 đến n.

Đối với mỗi người bán, chúng tôi cập nhật cây:

tree.update(L, R, C); 

Cuối cùng, để có được giá trị tối thiểu cho mục i, chúng tôi truy vấn các cây:

tree.getMin(i, i); 

Khi cả hai update và getMin có thời gian độ phức tạp O (log n), độ phức tạp thời gian cho toàn bộ chương trình là O (max (m, n) log n). Bạn không cần sửa đổi bất cứ điều gì từ việc triển khai thực hiện Phân đoạn gốc.