首页 > 代码库 > 【Luogu1843】奶牛晒衣服
【Luogu1843】奶牛晒衣服
点此进入原题
算法:二分答案
题解:
本题算法就是二分所需的时间啦
二分答案的难点大部分都在check函数上吧
然而我居然把二分模版打错了好囧啊
总的来说这题还是不难的啊~
代码:
#include<cstdio> const int N=500005; int n,a,b,t[N],l=0,r=N; bool check(int x) { int ret=x; //x-ret表示需要的烘干机烘干的天数。 for(int i=1;i<=n;i++) { int tmp=t[i]-a*x; //tmp表示一件衣服x天自然烘干后的湿度 if(tmp>0) ret-=(tmp/b+(tmp%b!=0)); //如果自然未烘干,则需要tmp/b(上取整)天来用烘干机烘干 if(ret<0) return false; //如果烘干机烘干衣服x天不够,就return false。 } return true; } int main() { scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++) scanf("%d",&t[i]); while(l<=r) //二分答案 { int m=(l+r)/2; if(check(m))r=m-1; //注意:如果答案符合要求就调整右边界,使区间里的值更小 else l=m+1; } printf("%d",r+1); //注意这里输出右边界啊(蒟蒻的我当时就这里错了QAQ) }
【Luogu1843】奶牛晒衣服
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。