POJ 1064 Cable master(二分答案)

嗯...

题目链接:http://poj.org/problem?id=1064

其实这是一道很好想的二分答案的一道题...

二分的区间就是1~max_l,从1开始是因为所有小于1的都需要按0计算,没必要讨论了...

每次二分出来的答案看它能否把电缆切成大于等于k块,如果可以,我们不能保证它是最优的答案,所以要向更大的地方二分;如果现在都不可以,我们必须向更小的地方二分,才有可能可以。

这道题注意二分一般在整数中二分,所以我们先把它们都乘100,如果要求精度更高,则乘的数更大,然后再整数二分,最后输出的时候再除回去即可...注意初始化...

AC代码:

 #include<cstdio>
#include<iostream> using namespace std; int ans, n, k, a[], max_l; inline void er_fen(){
int l = , r = max_l;
while(l <= r){
int cnt = ;
int mid = (l + r) >> ;
for(int i = ; i <= n; i++){
cnt += a[i] / mid;
}
if(cnt >= k){
ans = max(ans, mid);
l = mid + ;
}
else r = mid - ;
}
} int main(){
while(scanf("%d%d", &n, &k) != EOF){
max_l = -, ans = ;
for(int i = ; i <= n; i++){
double len;
scanf("%lf", &len);
a[i] = len * ;
max_l = max(max_l, a[i]);
}
er_fen();
printf("%.2f\n", (double) ans / 100.0);
}
return ;
}

AC代码

上一篇:Spring 注解@Transactional


下一篇:Bootstrap3-技巧之解决Bootstrap模态框切换时页面抖动 or页面滚动条