Chặt cây

Xem dạng PDF
Gửi bài giải
Điểm: 15,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
admin
Người đăng:
admin
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có N cây gỗ, có chiều cao lần lượt là ~A_1,A_2,...,A_N~. Bạn cần lấy một lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt tất cả những phần thừa của các cây có độ cao lớn hơn H.

Yêu cầu: Hãy tìm giá trị H lớn nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.

Input:

  • Dòng 1 chứa 2 số nguyên N và M .
  • Dòng 2 chứa N số nguyên ~A_1,A_2,...,A_N~, là chiều cao mỗi cây gỗ tương ứng. Giả sử luôn tồn tại cách chặt.

Output:

  • Số H duy nhất là kết quả bài toán trên.

Example:

Input:

4 7
20 15 10 17

Output:

15
Giải thích:  
Cây 1 chặt được (20-15)=5.
Cây 4 chặt được (17-15)=2.
Tổng số gỗ chặt được nếu H=15 là 7.

Constraints:

~1 \le N \le 2.10^5 ; 1 <= M <= 2.10^6 ; A_i \le 10^5~

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 7
    Shinoz  đã bình luận lúc 31, Tháng 8, 2023, 4:17 ← sửa 2

    Solution by Shinoz

    Mình viết cái này ra để một số bạn chưa hiểu hoặc không biết làm có thể hiểu và bắt đầu tiếp xúc với tham lam (aka Greedy)

    Đây không hoàn toàn là code mình tự nghĩ ra, mà đa số là được thầy Sơn giảng và giải thích

    Input 1:

    4 7
20 15 10 17

    Output 1:

    15

    Idea:

    1.Khai báo: n, m, sum, s, k, a[] (int)

    s = sum = a[0] = 0

    2.Dùng biến sum để tính tổng các phân tử A[1], A[2], A[3],...A[n]

    3.Sắp xếp mảng theo thứ tự tăng dần

    4.Chạy vòng lặp từ i = 1 đến n:

    Cộng vào s: tổng độ cao các cây có độ cao chênh lệnh của cây thứ i

    Khi đó ta có:

    1. Độ cao chênh lệch của cây thứ i: a[i] - a[i-1]

    2. Các cây có độ chênh lệnh đó: n-i+1

    -> Tổng = (a[i] - a[i-1])*(n - i + 1)

    Kiểm tra xem nếu hiệu của sum và s bé hơn m thì break vòng lặp

    5.Sau đó trừ s đi tổng các cây có độ chênh lệch thứ i lúc chạy xong vòng lặp

    ( Vì chỉ kiểm tra trường hợp bé hơn nên dù có bằng m thì cũng sẽ chạy thêm 1 bước nữa nên ta phải trừ s đi (a[i] - a[i-1])*(n - i + 1); Vầ cũng trường hợp đó nên ta có đáp án "chưa xác định" của bài toán là a[i-1] )

    6.Lúc này ta có thể thấy rằng:

    sum - s - m sẽ là phần phần thừa của đáp án "chưa xác định" (Chứng minh ở phía dưới) nên ta chỉ việc chia sum - s - m đi n - i + 1 sau đó cộng vào cho a[i-1] và in kết quá ra.

    Chứng minh sum - s - m là phần thừa

    Ta sẽ xét ví dụ khác ví dụ đã cho trên vì ta thấy ans ở đây là 15 nên phần thừa sẽ bằng 0.

    Input 2:

    5 20
4 42 40 26 46

    Output 2:

    36

    sum: 158

    sort: 4 26 40 42 46

    for:

    i = 1: s = 0 + 20 = 20; 158 - 20 = 138 >= m (20)

    i = 2: s = s + 88 = 108; 158 - 108 = 50 >= m (20)

    i = 3: s = s + 42 = 150; 158 - 150 = 8 < m (20) (break)

    s = s - 42 = 108;

    (lúc này ans = a[i-1] = 26)

    xét ans = 26:

    (40 + 42 + 46) - 26*3 = 50 = 158(sum) - 108(s) > 20 (thừa 30)

    -> phần thừa = sum - s - m = 30

    -> true <=> ans + 10 (= 36 theo op)

    -> ans = a[i-1] + ((sum - s - m) div (n-i+1))

    Code C++ mẫu code

    Chặt nhị phân khi nào rảnh mình sẽ up sol


  • 1
    Shinoz  đã bình luận lúc 25, Tháng 8, 2023, 17:28 ← sửa 2

    .