烘烤机（最简单解法）

380 阅读 0 评论 0 点赞

原题链接：烤干机

###原理
看到这个题，最直接的解法肯定应该枚举晾干所用时间time，然后判断当前的time是否足够衣服完全晾干。
判断方法为：
设当前晾干所用时间为time，晾干第i件衣服要用烘干机xi分钟，自然晾干时间为time-xi，则烘干第i件衣服需要满足：A*(time-xi)+xi*(A+B)>=clothes[i]，解得：xi>=ceil((clothes[i]-A*time)/B)（ceil为取上限）
判断sum(x)是否<=time即可判断time时间是否可以晾干所有衣服
```c++
bool isok(int time){
    int col=0;
    for(int i=0;i<n;i++){
        if(clothes[i]-A*time<=0)//注意这里要特判一下(大家可以思考一下为什么)
            continue;
        if((clothes[i]-A*time)%B==0){
            col+=(clothes[i]-A*time)/B;
        }else{
            col+=(clothes[i]-A*time)/B+1;
        }
    }
    return col<=time;
}
```
但枚举time会发现超时了，我们这是应该想到：枚举->二分
这样我们就不用从小到大一个一个地枚举，直接将时间复杂度降低为O(log2n)
###完整代码
```c++
#include <bits/stdc++.h>
using namespace std;
int n,A,B,clothe;
vector<int>clothes;
bool isok(int time){
    int col=0;
    for(int i=0;i<n;i++){
        if(clothes[i]-A*time<=0)
            continue;
        if((clothes[i]-A*time)%B==0){
            col+=(clothes[i]-A*time)/B;
        }else{
            col+=(clothes[i]-A*time)/B+1;
        }
    }
    return col<=time;
}
int main(){
    int max_clothe=0;
    cin>>n>>A>>B;
    for(int i=0;i<n;i++){
        cin>>clothe;
        clothes.push_back(clothe);
        max_clothe=max(max_clothe,clothe);//更新最大衣服水量
    }
	//将最大衣服水量作为二分的最大值
    int l=1,r=max_clothe,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(isok(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}
```

0.0分

3 人评分

本文分类：题解列表
浏览次数：380 次浏览
发布日期：2022-02-04 17:59:09
本文链接：https://blog.dotcpp.com/a/83478

上一篇 > Hifipsysta-1142题-C语言训练-立方和不等式（C++代码）
下一篇 > python-倍数问题

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

烘烤机（最简单解法）

评论列表共有 0 条评论

发表评论取消回复

烘烤机（最简单解法）

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复