1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量:n为衣服总数量,a为自然烘干速率(每秒降低a点湿度),b为烘衣机额外烘干速率 int n,a,b; // [2] 存储每件衣服初始湿度的数组,数组大小适配题目n≤5e5的范围要求 int arr[500100]; // [3] 自定义比较函数:实现数组降序排序,湿度大的衣服优先计算,方便后续剪枝 bool cmp(int x,int y){ return x>y; } int main() { // [4] 输入核心参数:衣服数量、自然烘干速率、烘衣机额外烘干速率 cin>>n>>a>>b; // [5] 循环输入每件衣服的初始湿度,存入数组arr for(int i=1;i<=n;i++) cin>>arr[i]; // [6] 对衣服湿度进行降序排序,优先处理高湿度衣服,快速触发剪枝逻辑 sort(arr+1,arr+n+1,cmp); // [7] 初始化二分查找边界:left为最小尝试时间1,right为单衣自然烘干的最大时间(初始上界) // [8] min_time记录烘干所有衣服的最小总时间,初始化为整型极大值,确保能被有效值覆盖 int left=1,right=arr[1],min_time=INT_MAX; // [9] 整数二分主循环:寻找能烘干所有衣服的最小总时间 while(left<=right){ // [10] 计算当前尝试的总时间mid,用left+(right-left)/2避免整数相加溢出(原代码标注为洗衣机时间,按标注保留) int mid=left+(right-left)/2;//mid-使用洗衣机的时间 // [11] sum统计所有衣服需要使用烘衣机的总时间,用于后续可行性判断 int sum=0;//统计使用洗衣机的时间 // [12] 遍历所有衣服,计算当前mid下的烘衣机总使用时间 for(int i=1;i<=n;i++){ // [13] 计算代码中定义的烘衣机需处理湿度值 int need=arr[i]-mid*a; // [14] 若当前值≤0,代码逻辑中认为无需使用烘衣机,跳过当前衣服 if(need<=0){ continue; } // [15] 计算单件衣服需要的烘衣机时间,无法整除则向上取整 if(need % b==0){ sum+=need/b; }else{ sum+=need/b+1; } // [16] 剪枝:烘衣机总时间已超过上限,无需继续计算后续衣服,直接终止循环 if(sum>mid) break; } // [17] 判断当前mid时间是否可行:烘衣机总使用时间≤总时间mid(同一时间仅能烘1件) if(sum<=mid){ min_time=mid; // [18] 记录当前可行的最小总时间 right=mid-1; // [19] 尝试更小的总时间,调整二分右边界 }else{ left=mid+1; // [20] 当前时间不足,需要更大的总时间,调整二分左边界 } } // [21] 输出烘干所有衣服的最小总时间 cout<<min_time; return 0; }
- 1
信息
- ID
- 1227
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 5
- 已通过
- 1
- 上传者