Hàng rào

Điểm: 800 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, ~~Scratch~~, Sed, ~~Swift~~, TCL, Turing, VB, Zig

CodeTN có $N$ thanh gỗ, thanh gỗ thứ $i$ có độ dài là $a_{i}$ . Anh ấy quyết định dùng số gỗ này để xây hàng rào cho ngôi nhà.

Để xây hàng rào ngôi nhà của cậu ấy, chúng ta phải cần ít nhất $K$ thanh gỗ độ dài bằng nhau. Vì vậy, các thanh gỗ có thể được cắt ra thành nhiều thanh gỗ độ dài nhỏ hơn.

Vì muốn an ninh của ngôi nhà được đảm bảo CodeTN muốn rằng những thanh gỗ này phải: "Càng cao càng tốt". Bạn hãy giúp CodeTN tìm ra độ dài lớn nhất có thể của những thanh gỗ này nhé.

$Input$

Dòng đầu tiên chứa hai số nguyên dương $N$ , $K$ , lần lượt là số thanh gỗ mà CodeTN có và số thanh gỗ cần thiết để xây hàng rào cho nhà cậu ấy.
Dòng thứ 2 chứa $N$ số, thanh gỗ thứ $i$ có độ dài là $a_{i}$ .

$Output$

Một số duy nhất là kết quả của bài toán.
Kết quả cần được in chính xác $2$ số chữ số thập phân.

$Constraint$

$N \leq 10^{6}$ .
$a_{i}$ , $K \leq 10^{9}$ .

$Subtask$

Subtask $1$ ( $20 %$ số điểm): $n \leq 10$ .
Subtask $2$ ( $30 %$ số điểm): $a_{i} \leq 1000$ .
Subtask $3$ ( $50 %$ số điểm): Không có giới hạn gì thêm.

$Sample Input$

Copy

3 4
2 3 8

$Sample Output$

Copy

2.66

Bình luận

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

-1

vandung666 đã bình luận 3:57:44 ch, 13/02/2025

include <iostream>

include <vector>

include <iomanip>

include <algorithm>

include <cmath>

using namespace std;

int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

Copy

int N, K;
cin >> N >> K;

vector<double> wood(N);
double maxLength = 0.0;
for (int i = 0; i < N; i++){
    cin >> wood[i];
    maxLength = max(maxLength, wood[i]);
}
double lo = 0.0, hi = maxLength;
for (int iter = 0; iter < 100; iter++){
    double mid = (lo + hi) / 2.0;
    long long count = 0;
    for (int i = 0; i < N; i++){
        count += static_cast&lt;long long>(wood[i] / mid);
    }
    if(count >= K)
        lo = mid;
    else
        hi = mid;
}

double ans = floor(lo * 100) / 100.0;

cout << fixed << setprecision(2) << ans << "\n";
return 0;

} code co ban cua mik