CutRopes

Problem Statement

有 $N$ 条绳子，它们的长度分别为 $L_i$。如果从它们中切割出 $K$ 条长度相同的绳子，这 $K$ 条绳子每条最长能有多长？答案保留到小数点后 $2$ 位(直接舍掉 $2$ 位后的小数)。

Input

第一行两个整数 $N$ 和 $K$，接下来 $N$ 行，描述了每条绳子的长度 $L_i$ 。

Output

切割后每条绳子的最大长度。答案与标准答案误差不超过 $0.01$ 或者相对误差不超过 $1%$ 即可通过。

Sample Input

Sample Output

1

2.00

Constraints

对于 $100%$ 的数据 $0<L_i\leq 100000.00,0<n\leq 10000,0<k\leq 10000$

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


const int N = 1e4+100;
const int M = 0; 
int n,k;
double rope[N];
bool check(double x)
{
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        ans += (int)(rope[i]/x);
    }
    return ans >= k;
}
void solve()
{
    cin >> n >> k;
    double l = 0,r = 0,mid;
    for(int i=1;i<=n;i++)
    {
        cin >> rope[i];
        r = max(r,rope[i]);
    }
    while(l+0.001<r)
    {
        mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    if(check(r))
    {
        l = r;
    }
    cout << fixed << setprecision(2) << l << endl;
}