郑州汉狮公司做网站,wordpress获取文章链接,简洁大气的网站模板,化妆品网站方案P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿#xff0c;为牛宝宝晒衣服就成了很不爽的事情。于是#xff0c;熊大妈请你#xff08;奶牛#xff09;帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间…P1843 奶牛晒衣服 【贪心】 题目背景 熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿为牛宝宝晒衣服就成了很不爽的事情。于是熊大妈请你奶牛帮助她完成这个重任。 题目描述 一件衣服在自然条件下用一秒的时间可以晒干 aa 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 b 点湿度一秒晒干 ab 湿度但在同一时间内只能烘一件衣服。现在有 n 件衣服第 i 衣服的湿度为 wi 保证互不相同要你求出弄干所有衣服的最少时间湿度为 0 为干 。 输入格式 第一行三个整数分别为 n,a,b。 接下来 2 到 n1 行第 i 行输入 wi 。 输出格式 一行弄干所有衣服的最少时间。 输入输出样例 输入 #1 3 2 1 1 2 3 输出 #1 1 输入 #2 4 2 3 8 5 7 9 输出 #2 3 说明/提示 样例解释 让机器烘第三件衣服即可一秒完成。 数据范围 1≤wi ,a,b,n≤5×10^5
贪心算法操作过程
最少时间取决于最后一件被弄干的衣服的时间。每次找出剩余的湿度最大的衣服使用烘干机。用大根堆维护衣服的剩余湿度。时间复杂度为Onlogn。
#include bits/stdc.h
using namespace std;
int n,a,b;
int main()
{ cinnab;priority_queueint q;for(int i1,x;in;i){cinx;q.push(x);}int tpxq.top();q.pop();int res0;while(tpxres*a){res;q.push(tpx-b);tpxq.top();q.pop();}coutres;return 0;
}
