Chặt cây xây nhà

Submit solution
Points: 3 (partial)
Time limit: 1.0s
JAVA11 2.0s
Memory limit: 250M
Author:
cotyey
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Bob là một thợ mộc tài hoa. Hiện tại anh đang có kế hoạch xây dựng một căn nhà toàn bộ bằng gỗ. Biệt thự được xây bởi các khúc gỗ khác nhau và tổng độ dài của các thanh gỗ là L.

Để lấy các khúc gỗ đó, anh ấy cần vào rừng và chặt cây. Khu rừng gần chỗ anh có N cây với độ cao khác nhau. Bob sẽ dùng một cái máy cưa đặc biệt, nó có thể cắt một lượt qua tất cả các cây.

Đầu tiên, anh ấy sẽ chọn một độ cao cố định là H, sau đó dùng máy cưa đặc biệt để cắt một đường theo độ cao H này trên các cây có độ cao lớn H.

Ví dụ: các cây có độ cao lần lượt là: 10,16,17,15. Chọn H bằng 15. Do đó, cây thứ 2,3 sẽ được cắt và tổng độ dài các khúc gỗ thu được là 1+2=3.

Cho độ cao của các cây trong rừng và giá trị L. (Tổng độ dài của các khúc gỗ cần). Hãy giúp Bob tìm giá trị lớn nhất của H thỏa mãn rằng Bob chỉ cần dùng máy cắt đúng một lượt để thu được số các khúc gỗ cần thiết.

Chú ý: Tổng độ dài các khúc gỗ có thỏa mãn có thể lớn hơn L (hay nói cách khác L ≤ tổng độ dài).

Input

Dòng đầu tiên chứa một số nguyên mô tả số lượng cây N (1≤N≤106) và L là tổng độ dài của các khúc gỗ cần dùng (1≤L≤2∗109).

Dòng tiếp theo chứa N số tự nhiên h[i] là độ cao tương ứng của các cây (h[i]<109). Tổng độ cao của các cây lớn hơn hoặc bằng L.

Output

Một số nguyên duy nhất: giá trị độ cao lớn nhất mà tại đó Bob cắt đúng một đường đề thu được các khúc gỗ thỏa mãn.

Example

Input 1:

Copy
3 6
1 2 3

Output 1:

Copy
0

Input 2:

Copy
4 10
10 15 12 13

Output 2:

Copy
10

Input 3:

Copy
4 1
5 5 5 5

Output 3:

Copy
4

Comments


  • 1
    vqhuy18  commented on Aug. 2, 2024, 9:13 a.m.

    chặt nhị phân ^^


  • -1
    Hoan_CNTT_VA2_K61  commented on March 17, 2022, 5:30 a.m. ← edit 3

    tham khảo:

    dùng tạm map :3

    Copy
    #include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int n, L, cnt=0, sum=0;
    cin >> n >> L;
    map<int,int>a;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        a[x]++;
    }
    auto it=a.end();
    it--;
    int d=it->first; // khúc gỗ dài nhất
    while(d){
        if(d==it->first){ // nếu tìm được khúc gỗ thấp hơn
            cnt+=it->second; // số khúc gỗ đang bị chặt
            it--;
        }
        sum += cnt;
        d--;
        if(sum>=L){cout << d; return 0;}
    }
    return 0;
}

  • 10
    cotyey  commented on Jan. 9, 2022, 1:40 p.m.

    Chặt nhị phân ^^