jimore

用户名：uq_30465888842

访问量：9805

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	177
经　　验	6850
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：449

求一个很大的数的所有质因子（新方法）
浏览：247

佩尔方程——模板题
浏览：227

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

烘烤机（最简单解法）

　　作者: jimore　　　　发表时间：2022-02-04 17:59:09 浏览：245　|　评论：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 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

简单的a+b （C语言代码）

矩形面积交（Java代码）

计算质因子（C++代码）

烘烤机（最简单解法）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

勾股数（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

数列排序（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

三进制小数（C语言代码）

jimore

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

简单的a+b （C语言代码）

矩形面积交 （Java代码）

计算质因子 （C++代码）

烘烤机（最简单解法）

评论区

精彩推荐

A+B for Input-Output Practice (II) （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

勾股数 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

数列排序 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

三进制小数 （C语言代码）

矩形面积交（Java代码）

计算质因子（C++代码）

　　评论区

C二级辅导-阶乘数列（C语言代码）

勾股数（C语言代码）

数列排序（C语言代码）

三进制小数（C语言代码）