Aggressive Cows

Q: Độ phức tạp thời gian của bài toán Aggressive Cows là gì?

Việc sắp xếp mất O(n log n) và tìm kiếm nhị phân mất O(n log D) , trong đó D là khoảng cách giữa các vị trí chuồng chia cho k-1 . Ngoài bản sao đã sắp xếp, bộ nhớ cần dùng là O(1) .

Q: Tại sao con bò đầu tiên luôn vào chuồng ngoài cùng bên trái?

Chọn một cách sắp xếp bất kỳ phù hợp rồi chuyển con bò ở ngoài cùng bên trái đến chuồng ngoài cùng bên trái. Con bò đó chỉ di chuyển ra xa những con còn lại, vì vậy không khoảng cách nào bị thu hẹp, và có một cách sắp xếp tối ưu sử dụng chuồng ngoài cùng bên trái.

Q: Làm thế nào để nhận biết tìm kiếm nhị phân trên đáp án?

Đề bài hỏi giá trị lớn nhất hoặc nhỏ nhất để một điều gì đó khả thi. Kiểm tra một giá trị dễ hơn nhiều so với tìm giá trị tốt nhất, và đáp án chỉ đổi một lần khi giá trị tăng lên. Ở đây, giá trị là khoảng cách và cách kiểm tra là sắp xếp tham lam.

Trung bìnhTìm kiếm nhị phân Sắp xếp Tham lam

+10

Một chuồng trại có các ô chuồng nằm dọc theo một đường thẳng, và stalls[i] là vị trí của ô chuồng i. Các vị trí đều khác nhau và không theo thứ tự cụ thể nào. Bạn phải đặt k con bò vào k ô chuồng khác nhau. Bò sẽ đánh nhau khi đứng gần nhau, vì vậy bạn muốn khoảng cách giữa hai con bò gần nhau nhất lớn nhất có thể.

Trả về giá trị lớn nhất có thể của khoảng cách nhỏ nhất giữa bất kỳ hai con bò nào.

Hàm

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: các vị trí quầy hàng riêng biệt, theo thứ tự bất kỳ
kinteger: số con bò cần đặt
Trả vềinteger: khoảng cách nhỏ nhất lớn nhất có thể giữa hai con bò

Ràng buộc

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
Tất cả vị trí trong stalls đều khác nhau.
2 ≤ k ≤ stalls.length

Ví dụ

Đầu vào: stalls = [10, 1, 7, 4, 15]k = 3
Đầu ra: 6
Giải thích: Các con bò ở vị trí 1, 7 và 15 cách nhau lần lượt 6 và 8 đơn vị. Khoảng cách 7 không đạt: sau vị trí 1, con bò tiếp theo được đặt ở vị trí 10, và không có ô chuồng nào ở vị trí 17 trở đi.

Câu hỏi mở rộng

Điều gì thay đổi nếu các quầy hàng nằm trên một vòng tròn, để quầy cuối cùng cũng là hàng xóm của quầy đầu tiên?

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

Hãy chọn một khoảng cách rồi hỏi: liệu k con bò có thể đứng sao cho khoảng cách giữa mỗi cặp ít nhất bằng khoảng cách đó không? Chỉ cần duyệt tham lam một lượt qua các chuồng đã sắp xếp là có thể trả lời câu hỏi này. Khi khoảng cách tăng lên, câu trả lời sẽ chuyển từ có sang không đúng một lần, vì vậy tìm kiếm nhị phân sẽ tìm ra khoảng cách lớn nhất mà câu trả lời vẫn là có.

Sắp xếp, rồi lần lượt thử từng khoảng trống

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

Ý tưởng

Sắp xếp các vị trí. Hai con bò gần nhau nhất luôn đứng cạnh nhau, vì vậy khoảng cách g phù hợp khi khoảng cách giữa mọi cặp bò đứng cạnh nhau ít nhất là g.

Để kiểm tra một khoảng cách, đặt một con bò vào chuồng ngoài cùng bên trái, sau đó đặt mỗi con tiếp theo vào chuồng cách vị trí của con bò cuối cùng ít nhất g. Cách đặt tham lam này xếp được nhiều bò nhất có thể. Xếp bất kỳ cách đặt phù hợp nào từ trái sang phải: con bò thứ i trong cách đặt tham lam không bao giờ nằm bên phải con bò thứ i trong cách đặt đó, vì vậy cách đặt tham lam luôn tìm được chuồng cho con bò tiếp theo không muộn hơn.

Khoảng cách 1 luôn phù hợp, vì vậy hãy thử g = 2, 3, ... và dừng ở khoảng cách đầu tiên chỉ xếp được ít hơn k con bò. Trong ví dụ đầu tiên, khoảng cách 6 xếp được 3 con bò còn khoảng cách 7 chỉ xếp được 2 con, nên đáp án là 6.

Với hai con bò và các chuồng ở vị trí 0 và 10^9, cần khoảng 10^9 lượt duyệt qua 5000 chuồng, tức 5 × 10^12 bước.

Thuật toán

Sắp xếp các vị trí.
Viết phần kiểm tra khoảng cách g: đặt một con bò ở pos[0], sau đó đặt một con bò ở mỗi chuồng sao cho pos[i] - last ≥ g, đồng thời đếm số bò.
Bắt đầu với gap = 1.
Trong khi phần kiểm tra gap + 1 có thể đặt ít nhất k con bò, hãy tăng gap thêm 1.
Trả về gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Tìm kiếm nhị phân trên khoảng cách

Ý tưởng

Cách bố trí có mọi khoảng cách ít nhất là g+1 cũng có mọi khoảng cách ít nhất là g, nên các lần kiểm tra lần lượt cho kết quả có, ..., có, không, ..., không. Tìm kiếm nhị phân tìm ra giá trị có cuối cùng.

Bắt đầu tìm kiếm từ lo = 1, giá trị này luôn thỏa mãn, đến hi = độ dài đoạn chia cho k-1, làm tròn xuống: k con bò tạo ra k-1 khoảng cách trong đoạn, nên khoảng cách nhỏ nhất không thể lớn hơn giá trị đó. Khi kiểm tra đạt, đặt lo = mid, vì vậy phải làm tròn mid lên; nếu làm tròn xuống, lo = 5 và hi = 6 sẽ lặp mãi.

Ở ví dụ đầu tiên, độ dài đoạn là 14 và k = 3, nên hi = 7. Khoảng cách 4 đạt, khoảng cách 6 đạt, khoảng cách 7 không đạt, và phạm vi thu hẹp lại còn 6.

Phạm vi có độ rộng đến 10^9 sẽ thu hẹp sau khoảng 30 lần kiểm tra với 5000 chuồng, tổng cộng khoảng 150,000 bước.

Thuật toán

Sắp xếp các vị trí.
Đặt lo = 1 và hi = (pos[n-1] - pos[0]) / (k-1), làm tròn xuống.
Khi lo < hi, lấy mid = lo + (hi - lo + 1) / 2.
Nếu phép kiểm tra tham lam tại mid đặt được ít nhất k con bò, đặt lo = mid; nếu không, đặt hi = mid - 1.
Trả về lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

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

Bỏ qua bước sắp xếp. Với danh sách chưa được sắp xếp [10, 1, 7, 4, 15] và khoảng cách 6, lượt kiểm tra bắt đầu tại 10, không tìm thấy chuồng nào tiếp theo cách nó ít nhất 6, nên chỉ tính được một con bò.
Làm tròn mid xuống trong khi một lượt kiểm tra gán lo = mid. Khi hi = lo + 1, phạm vi không còn thu hẹp và vòng lặp không bao giờ kết thúc.
Kiểm tra xem có đúng k con bò hay không. Với khoảng cách 1, ví dụ đầu tiên xếp được 5 con bò, nhiều hơn 3, nhưng khoảng cách đó vẫn phù hợp; hãy kiểm tra count ≥ k.
Bắt đầu đếm số bò từ 0. Con bò ở chuồng ngoài cùng bên trái cũng được tính, nên số đếm bắt đầu từ 1.

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

Độ phức tạp thời gian của bài toán Aggressive Cows là gì?

Việc sắp xếp mất O(n log n) và tìm kiếm nhị phân mất O(n log D), trong đó D là khoảng cách giữa các vị trí chuồng chia cho k-1. Ngoài bản sao đã sắp xếp, bộ nhớ cần dùng là O(1).

Tại sao con bò đầu tiên luôn vào chuồng ngoài cùng bên trái?

Chọn một cách sắp xếp bất kỳ phù hợp rồi chuyển con bò ở ngoài cùng bên trái đến chuồng ngoài cùng bên trái. Con bò đó chỉ di chuyển ra xa những con còn lại, vì vậy không khoảng cách nào bị thu hẹp, và có một cách sắp xếp tối ưu sử dụng chuồng ngoài cùng bên trái.

Làm thế nào để nhận biết tìm kiếm nhị phân trên đáp án?

Đề bài hỏi giá trị lớn nhất hoặc nhỏ nhất để một điều gì đó khả thi. Kiểm tra một giá trị dễ hơn nhiều so với tìm giá trị tốt nhất, và đáp án chỉ đổi một lần khi giá trị tăng lên. Ở đây, giá trị là khoảng cách và cách kiểm tra là sắp xếp tham lam.

def aggressiveCows(stalls, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

stalls = [10, 1, 7, 4, 15]
k = 3

Đầu ra mong đợi