关于二分
定义:把答案所在的区间范围逐渐缩小,直到区间内只有一个答案。
由手动模拟可知道(数学答案都这样hhc)
mid 用(l + r) / 2计算时,如果程序中有l = mid ,程序会陷入死循环。
mid 用(l + r + 1) / 2计算时,如果程序中有r = mid ,程序会陷入死循环。
1. 程序中不要同时出现l = mid, r = mdi这两条语句。
2. 如果程序中出现了l = mid,mid的值用 (l + r + 1) / 2计算。
3. 如果程序中出现了r = mid,mid的值用((l + r) / 2计算。
//模板
bool check(int x) {// 判断x是否满足条件
...
}
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r){
while (l < r){
int mid = l + (r - l >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r){
while (l < r){
int mid = l + (r - l + 1 >> 1);
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
//该题代码
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,a[MAXN];
bool check(double x){
int ans = 0;
for(int i = 1; i<= n; i++){
ans += (a[i] / x);//能砍出的数目
if(ans >= m) return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
double l = 0 ,r = 1e9;
while(r - l > 0.001){
double mid = l + (r-l)/2.0;
if(check(mid)) l = mid ;//存在
else r = mid ;//不存在
}
printf("%.2lf",l);
return 0;
}