#include <algorithm>
#include <iostream>
using namespace std;
int Find(int *a,int n,double mid)
{
int k = 0;
for(int i=n-1;i>=0;i--)
k += int(a[i]/mid);
return k;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int a[n];
sort(a,a+n);
double ans = 0;
for(int i=0;i<n;i++)
scanf("%d",&a[i]),ans += a[i];
ans/m;
double le = 0,ri = ans;
for(int i=0;i<1000;i++)
{
double mid = (le+ri)/2;
int num = Find(a,n,mid);
if(num >= m)
le = mid;
else
ri = mid;
}
printf("%.2f",(le+ri)/2);
return 0;
}
说下思路吧…我也是第一次写这种不太确定是二分的题…
由于需要求解出最长那个绳子…我们找一下现有的算法:爆搜,动态规划,贪心…
好像都不怎么合适…这时候我们就需要想到二分答案…
这道题解法还是比较简单的,关键在于想的过程…
去年CCPC有道题也是二分,虽然我没参加比赛,但是在旁边看着题还是对这道题印象深刻…
感兴趣的可以去做下—Defuse the Bombs(题目名字,百度就有)