1 条题解

  • 0
    @ 2026-2-4 16:28:16
    #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
    上传者