题目地址:http://poj.org/problem?id=1064
有N条绳子,它们的长度分别为Ai,如果从它们中切割出K条长度相同的绳子,这K条绳子每条最长能有多长。
二分绳子长度,然后验证即可。复杂度o(nlogm)
#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdbool.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define clr(x,y) memset(x,y,sizeof(x))
#define sqr(x) ((x)*(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define LL long long
#define INF 0x3f3f3f3f
#define A first
#define B second
const int N=+;
int n,k;
double a[N]; bool check(double len)
{
int num=;
for(int i=;i<n;i++) {
num+=(int)(a[i]/len);
}
return num>=k;
} void solve()
{
double lb=,ub=INF; scanf("%d%d",&n,&k);
for(int i=;i<n;i++) {
scanf("%lf",&a[i]);
} for(int i=;i<;i++) {
double mid=(lb+ub)/;
if(check(mid)) {
lb=mid;
} else {
ub=mid;
}
}
printf("%.2f\n",floor(ub*)/);
} int main()
{
solve(); return ;
}