题意分析

题目背景

本题属于二分查找与数值优化问题，描述如何从给定长度的电缆中切割出指定数量的等长电缆段，并最大化每段长度。

核心问题

1. 输入数据：
   • $N$：库存电缆数量（$1 \leq N \leq 10000$）。
   • $K$：所需电缆段数量（$1 \leq K \leq 10000$）。
   • 每根电缆的长度（$1 \text{米} \leq \text{长度} \leq 100 \text{公里}$，精度到厘米）。
2. 目标：找到满足$K$段切割条件的最大电缆段长度$L$（以厘米为单位，保留两位小数）。

约束条件

• 切割后的每段长度$L$必须$\geq 1 \text{厘米}$。
• 若无法满足$K \geq 1$段，输出0.00。

解题思路

1. 问题转换

• 单位统一：将所有电缆长度转换为厘米（乘以$100$），避免浮点数运算。
• 数学建模：设最大长度为$L$，则需满足：$$\sum_{i=1}^{N} \left\lfloor \frac{\text{length}_i}{L} \right\rfloor \geq K $$其中$\text{length}_i$为第$i$根电缆的长度。

2. 二分查找

• 搜索范围：
  • 左边界$l = 1 \text{厘米}$。
  • 右边界$r = \max(\text{length}_i)$。
• 可行性检查： 对于中间值$mid$，计算是否能切割出至少$K$段长度为$mid$的电缆。
  • 若可行，尝试更大的$L$（调整$l = mid$）。
  • 否则，尝试更小的$L$（调整$r = mid - 1$）。
• 终止条件：$l = r$，找到最大可行$L$。

3. 边界处理

• 无解情况：若$K=0$或所有电缆总长度不足$K \text{厘米}$，直接输出0.00。

算法实现

代码框架

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int a[10005];
bool cheak(int l)
{
   ll sum=0;
   int i;
   for(i=1;i<=n;i++)
   {
   	 sum+=a[i]/l;
   }
   return sum>=k;
} 
int main()
{
    cin>>n>>k;
    int i;
    double t;
    for(i=1;i<=n;i++) cin>>t,a[i]=int(t*100);
    
    if(cheak(1)==false)
    {
    	cout<<"0.00";
    	return 0;
	}
	
	int l = 1,r = 1e7;
	
	int mid;
	while(l<r)
	{
		mid = (l+r+1)/2;
		if(cheak(mid)) l = mid;
		else r = mid-1;
	}
	
	printf("%.2f",(double)l/100);
    return 0;
}

关键步骤

1. 输入处理：读取电缆数量$N$和需求$K$，转换长度为厘米。
2. 可行性检查：函数isFeasible验证当前长度$L$是否满足$K$段需求。
3. 二分查找：
   • 初始化边界$l=1$，$r=\max(\text{length}_i)$。
   • 循环调整边界，直到找到最大可行$L$。
4. 输出结果：将$L$转换回米单位并格式化输出。

复杂度分析

• 时间：$O(N \log (\max(\text{length}_i)))$，其中二分查找迭代次数为$\log (\max(\text{length}_i))$，每次检查$O(N)$。
• 空间：$O(N)$，存储电缆长度。