NOIP2012模拟试题【奶牛晒衣服】
2024-09-27 03:19:13
1.奶牛晒衣服(dry)
【问题描述】
在熊大妈英明的带领下,时针和它的同伴生下了许多牛宝宝。熊大妈决定给每个宝宝都穿上可爱的婴儿装。于是,为牛宝宝洗晒衣服就成了很不爽的事情。
圣人王担负起了这个重任。洗完衣服后,你就要弄干衣服。衣服在自然条件下用1的时间可以晒干A点湿度。抠门的熊大妈买了1台烘衣机。使用烘衣机可以让你用1的时间使1件衣服除开自然晒干的A点湿度外,还可烘干B点湿度,但在1的时间内只能对1件衣服使用。
N件的衣服因为种种原因而不一样湿,现在告诉你每件衣服的湿度,要你求出弄干所有衣服的最少时间(湿度为0为干)。
【输入】
第一行N,A,B;接下来N行,每行一个数,表示衣服的湿度(1≤湿度,A,B≤500000,1≤N≤500000)。
【输出】
一行,最少时间。
【样例】
dry.in
3 2 1
1
2
3
dry.out
1
【样例解析】
第1个时间内,用机器处理第3件衣服,此外,所有衣服自然晒干2。花费1时间全部弄干。
刚拿到题的时候以为是dp,TAT因为一大早就和和另一个妹子在看容斥原理,满脑子都是dp(/手动再见,我就是这么蠢)
后来才知道是非!常!简!单!的一个队列题!啊啊啊啊啊啊啊啊l(っ*´Д`)っ!
(为啥我这么蠢啊!)
因为随着时间的增加,只要没有晾干的衣服都会进行湿度-a的操作,所以我们可以直接用一个变量sum来记录总共要减去的湿度,就不需要每次都把每件衣服都减去a了
下面的代码有足够的注释=v=不再多说
#include<cstdio>
#include<cstring>
#include<queue> //***
#include<algorithm>
using namespace std;
priority_queue<int>q;//***
int n,a,b;
int w;
void read()
{
scanf("%d%d%d",&n,&a,&b);
int w;
for(int i=;i<=n;i++)
{
scanf("%d",&w);
q.push(w);//将湿度入队;
}
int sum=;
int t=;
while(!q.empty())//如果队列不为空,即还有衣服没晾干;
{
int k=q.top();
if(k<=sum){
printf("%d",t);
return;
}//如果无需烘干,即当前的自然晒干的湿度的总和>衣服的湿度,直接打印;
else{//需要烘干机;
q.pop();
k-=b;//烘干机操作后的湿度;
sum+=a;//自然晒干的湿度的总和等于这一次操作之前适度的总和加这一次的晒干的湿度;
t++;//时间加一;
q.push(k);//将k再次入队判断(因为k还没有晾干所以还需要更多的时间)
}
}
printf("%d",t);
}
int main()
{
freopen("dry.in","r",stdin);
freopen("dry.out","w",stdout);
read();
}
队列
最新文章
- javaMail
- springMVC+mybatis+spring整合案例
- 前端模块化开发之seaJs
- [ACM] poj 1064 Cable master (二分查找)
- Masonry第三方代码约束
- int(11)最大长度是多少,MySQL中varchar最大长度是多少(转)
- jqmobi 转换语言
- 高频交易:Solarflare组建超低延迟网络
- [Python学习笔记][第八章Python异常处理结构与程序调试]
- Ubuntu纯字符界面的一些设置
- React入门---开始前的准备(上)-2
- postman 第4节 切换环境和设置读取变量(转)
- MySQL中order by排序时,数据存在null咋办
- Spring Boot与消息
- java之JVM(二)
- 简简单单美化你Mac os x的终端配色
- 为什么黑客都不用鼠标?你听说过Linux吗?
- 通过jQuery实时监听表格行数变化
- STL进阶--狡猾的反向迭代器
- ArgumentException: 已添加了具有相同键的项。
热门文章
- uva 10391 Compound Words <;set>;
- Android 开发技术流程
- 【solr专题之四】在Tomcat 中部署Solr4.x
- css3的滤镜模糊的效果
- Find them, Catch them(POJ 1703 关系并查集)
- MySQL--mysqldump的权限说明
- 利用raspberry pi搭建typecho笔记(三) typecho nginx sqlite FAQ
- 开机时候系统总是提醒Android系统更新
- BZOJ 1065 奥运物流
- WPF笔记(1.9 样式和控件模板)——Hello,WPF!