Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

Tìm tổng nhỏ thứ k cho mỗi tập hợp con có thể

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 02:32:43 25 4
mua khóa gpt4 Nike


Lần trước tôi đã tìm thấy một vấn đề thú vị và bị mắc kẹt.

Cho n số a[1], ..., a[n] theo thứ tự tăng dần và số k (1 <= n,k <= 10^5).

Giả sử chúng ta sắp xếp mọi tập con có thể có của một dãy cho trước theo tổng.
Chúng ta phải tìm tổng của tập con thứ k như vậy.

Ví dụ:
n = 4, k = 8
a = {2, 7, 8, 15}

1: { 2 }, tổng = 2
2: { 7 }, tổng = 7
3: { 8 }, tổng = 8
4: { 2, 7 }, tổng = 9
5: { 2, 8 }, tổng = 10
6: { 7, 8 }, tổng = 15
7: { 15 }, tổng = 15
8: { 2, 15 }, tổng = 17
...
k = 8 nên đáp án = 17 (tập con {2,15}).

Tất nhiên, chúng tôi có thể tạo mọi tập hợp con có thể và toàn bộ giải pháp sẽ chạy trong thời gian O(2^n * n), nhưng tôi đang tìm kiếm thứ gì đó thông minh hơn - tuyến tính hoặc ít nhất là O(nk).

câu trả lời hay nhất

(Để đơn giản, giả sử các tập hợp con không trống. Việc xử lý các tập hợp con trống là một hoặc hai dòng.)

chỉ số đã cho S Một tập con không trống của S của những đứa trẻ được định nghĩa là S\{max(S)} U {max(S) + 1} Và SU {tối đa(S) + 1}. từ {1} Ban đầu, các mối quan hệ con tạo thành một cây bao gồm mọi tập hợp con khác rỗng của các số nguyên dương.

{1}
|
{2} {1,2}______
|
{3} {2,3} {1,3} {1,2,3}

Được khóa bằng tổng các phần tử mảng tương ứng, cây này là một đống tối thiểu. Nếu bạn đếm các khóa một cách cẩn thận (bằng cách cộng và trừ thay vì tính tổng từ đầu) và trì hoãn việc loại bỏ vùng heap tối thiểu, bạn sẽ thu được thuật toán thời gian O(k log k).

Về thuật toán - tìm tổng nhỏ thứ k cho mỗi tập hợp con có thể, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/33219712/

25 4 0
Bài viết khuyến nghị: java — logarit tự nhiên của hàm Bessel, tràn
Bài viết khuyến nghị: php - Tôi nên sử dụng công cụ tìm kiếm bên thứ ba nào (miễn phí)?
Bài viết khuyến nghị: SEO: Các bot của Google có thấy văn bản trong các div ẩn không
Bài viết khuyến nghị: Tìm số thứ n trong dãy tăng dần 0,2,4,6,8?
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress