Chocolate Distribution Problem

Q: Độ phức tạp thời gian của bài toán chia sô-cô-la là bao nhiêu?

Việc sắp xếp mất O(n log n) và việc trượt cửa sổ gồm m gói mất O(n) , nên tổng thời gian là O(n log n) . Bộ nhớ bổ sung là O(n) để tạo bản sao đã sắp xếp, hoặc O(1) ngoài phần sắp xếp nếu bạn sắp xếp trực tiếp dữ liệu đầu vào.

Q: Bài toán phân chia sô-cô-la có phải là bài toán cửa sổ trượt không?

Đúng vậy, một cửa sổ có kích thước cố định trên các gói đã sắp xếp. Khác với cửa sổ tính tổng tích lũy, bạn không cần cập nhật gì khi cửa sổ di chuyển: độ chênh lệch của mỗi cửa sổ chỉ cần tính bằng cách lấy gói đầu tiên trừ khỏi gói cuối cùng.

Q: Ta có thể giải bài toán phân phát sô cô la mà không cần sắp xếp không?

Kích thước ở đây tối đa là 10^5 , nên thuật toán sắp xếp đếm sắp xếp chúng trong thời gian O(n + 10^5) và lập luận tương tự vẫn đúng. Với kích thước không bị giới hạn, chỉ dùng phép so sánh thì không thể nhanh hơn O(n log n) : khi m = 2 , kết quả bằng 0 chính xác khi có hai gói bằng nhau, và trong trường hợp xấu nhất, cần chừng ấy phép so sánh để phát hiện phần tử trùng lặp.

DễSắp xếp Cửa sổ trượt

+10

Bạn có một số gói sô-cô-la, trong đó packets[i] là số viên sô-cô-la trong gói thứ i. Mỗi học sinh trong số m học sinh nhận đúng một gói, nên sẽ phát ra m gói khác nhau. Hãy chọn các gói sao cho chênh lệch giữa gói nhiều viên nhất và gói ít viên nhất được phát ra là nhỏ nhất có thể.

Viết một hàm có tên minDifference trả về chênh lệch nhỏ nhất có thể đó.

Hàm

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: số viên sô cô la trong mỗi gói
minteger: số học sinh, mỗi em nhận một gói
Trả vềinteger: chênh lệch nhỏ nhất có thể giữa gói lớn nhất và gói nhỏ nhất được phát

Ràng buộc

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Hai gói có thể đựng cùng số lượng sô-cô-la.

Ví dụ

Đầu vào: packets = [9, 3, 15, 7, 11, 4]m = 3
Đầu ra: 4
Giải thích: Sau khi sắp xếp, các gói hàng là 3, 4, 7, 9, 11 và 15. Cả 3, 4, 7 lẫn 7, 9, 11 đều có hiệu bằng 4, và không có bộ ba gói hàng nào gần nhau hơn.

Đầu vào: packets = [8, 1, 5]m = 3
Đầu ra: 7
Giải thích: Có ba học sinh và ba gói hàng, nên tất cả các gói hàng đều được phát và độ chênh lệch là 8 - 1 = 7.

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thử mọi nhóm gồm m gói hàng sẽ mất quá nhiều thời gian. Lựa chọn tốt nhất luôn là m gói hàng nằm cạnh nhau sau khi sắp xếp. Vì vậy, hãy sắp xếp một lần, rồi tìm hiệu nhỏ nhất giữa các gói hàng trong mọi cửa sổ gồm m gói liền kề chỉ với một lượt duyệt.

Sửa gói nhỏ nhất

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Cố định gói nhỏ nhất bạn phát, low. Để giữ gói lớn nhất nhỏ, hãy chọn m-1 gói nhỏ nhất có kích thước ít nhất bằng low. Khi đó, hiệu là kích thước gói nhỏ thứ m trong số các gói có kích thước ít nhất bằng low, trừ đi low. Thử từng gói làm low, bỏ qua gói nào có ít hơn m gói có kích thước bằng hoặc lớn hơn nó, rồi giữ lại hiệu nhỏ nhất.

Mỗi lựa chọn trong n lựa chọn sẽ lọc và sắp xếp tối đa n gói: O(n² log n). Với n = 10^4 kích thước khác nhau, riêng các lần sắp xếp đã cần khoảng 6 × 10^8 phép so sánh.

Thuật toán

Đặt best ở một giá trị mà không đáp án nào có thể vượt quá.
Với mỗi gói kẹo low, thu thập tất cả các gói có ít nhất low viên sô-cô-la rồi sắp xếp chúng.
Nếu có ít nhất m gói như vậy, lấy gói nhỏ thứ m trừ đi low để được một giá trị ứng viên.
Giữ giá trị ứng viên nhỏ nhất trong best rồi trả về giá trị đó.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Sắp xếp và trượt cửa sổ gồm m gói dữ liệu

Ý tưởng

Theo thứ tự đã sắp xếp, một cửa sổ sizes[i..i+m-1] có gói nhỏ nhất ở đầu và gói lớn nhất ở cuối, nên độ chênh lệch là sizes[i+m-1] - sizes[i].

Ta luôn có thể chọn một cửa sổ làm phương án tối ưu. Nếu phương án bỏ qua một gói nằm giữa gói nhỏ nhất và gói lớn nhất, hãy thay gói lớn nhất bằng gói đó. Gói nhỏ nhất vẫn giữ nguyên, còn gói lớn nhất chỉ có thể nhỏ đi, nên độ chênh lệch không bao giờ tăng. Lặp lại cho đến khi không còn khoảng trống nào.

Trong ví dụ đầu tiên, các cửa sổ gồm ba gói có độ chênh lệch lần lượt là 4, 5, 4 và 6, nên đáp án là 4. Sắp xếp tốn O(n log n) và trượt cửa sổ tốn O(n).

Thuật toán

Sắp xếp các gói theo thứ tự tăng dần vào sizes.
Đặt best bằng sizes[m-1] - sizes[0], cửa sổ đầu tiên.
Với mỗi điểm bắt đầu i từ 1 đến n-m, so sánh sizes[i+m-1] - sizes[i] với best và giữ lại giá trị nhỏ hơn.
Trả về best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Lỗi thường gặp và trường hợp biên

Kết thúc cửa sổ tại i+m thay vì i+m-1, khiến cửa sổ chứa m+1 gói.
Dừng sớm hơn một cửa sổ. Vị trí bắt đầu chạy từ 0 đến hết n-m. Với [1, 10, 20, 21] và m = 2, vòng lặp dùng i < n-m bỏ lỡ độ chênh lệch duy nhất bằng 1.
Bỏ qua bước sắp xếp. Trong [9, 3, 15, 7, 11, 4], ba gói đầu tiên có độ chênh lệch là 12, trong khi đáp án là 4.
Chỉ đo cửa sổ đầu tiên. Chọn m gói nhỏ nhất là một cách, nhưng nhóm tốt nhất có thể bắt đầu ở bất kỳ vị trí nào.
Sắp xếp các số dưới dạng văn bản. Trong JavaScript, sort() không có hàm so sánh sẽ xếp 100000 trước 9.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán chia sô-cô-la là bao nhiêu?

Việc sắp xếp mất O(n log n) và việc trượt cửa sổ gồm m gói mất O(n), nên tổng thời gian là O(n log n). Bộ nhớ bổ sung là O(n) để tạo bản sao đã sắp xếp, hoặc O(1) ngoài phần sắp xếp nếu bạn sắp xếp trực tiếp dữ liệu đầu vào.

Bài toán phân chia sô-cô-la có phải là bài toán cửa sổ trượt không?

Đúng vậy, một cửa sổ có kích thước cố định trên các gói đã sắp xếp. Khác với cửa sổ tính tổng tích lũy, bạn không cần cập nhật gì khi cửa sổ di chuyển: độ chênh lệch của mỗi cửa sổ chỉ cần tính bằng cách lấy gói đầu tiên trừ khỏi gói cuối cùng.

Ta có thể giải bài toán phân phát sô cô la mà không cần sắp xếp không?

Kích thước ở đây tối đa là 10^5, nên thuật toán sắp xếp đếm sắp xếp chúng trong thời gian O(n + 10^5) và lập luận tương tự vẫn đúng. Với kích thước không bị giới hạn, chỉ dùng phép so sánh thì không thể nhanh hơn O(n log n): khi m = 2, kết quả bằng 0 chính xác khi có hai gói bằng nhau, và trong trường hợp xấu nhất, cần chừng ấy phép so sánh để phát hiện phần tử trùng lặp.

def minDifference(packets, m):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

packets = [9, 3, 15, 7, 11, 4]
m = 3

Đầu ra mong đợi