做网站怎么样,wordpress邮件表单,asp.net 个人网站,最专业网站建设公司首选题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿#xff0c;为牛宝宝晒衣服就成了很不爽的事情。于是#xff0c;熊大妈请你#xff08;奶牛#xff09;帮助她完成这个重任。
题目描述
一件衣服在自然条件下用一秒的时间可以晒干 a 点湿度。抠门…题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿为牛宝宝晒衣服就成了很不爽的事情。于是熊大妈请你奶牛帮助她完成这个重任。
题目描述
一件衣服在自然条件下用一秒的时间可以晒干 a 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 b 点湿度一秒晒干 ab 湿度但在同一时间内只能烘一件衣服。现在有 n 件衣服第 i 衣服的湿度为 wi保证互不相同要你求出弄干所有衣服的最少时间湿度为 0 为干 。
输入格式
第一行三个整数分别为 n,a,b。 接下来 2 到n1 行第 i 行输入 wi。
输出格式
一行弄干所有衣服的最少时间。
输入输出样例
输入 #1复制
3 2 1
1
2
3
输出 #1复制
1
说明/提示
样例解释
让机器烘第三件衣服即可一秒完成。
解析
我们贪心每次烘干其时间最长的衣服。这时就需要维护大根堆每次烘干去最大值-b;
#includebits/stdc.h
using namespace std;
struct node{int a;bool operator (const node b) const{return a b.a;}
};
int main(){int n,a,b;cin n ab;priority_queuenode pq;for(int i 1;i n;i){int x;cin x;pq.push({x});}int time 0;int mx pq.top().a;while(mx time*a){//我们每次取最大的进行烘干 time;mx - b;pq.pop();pq.push({mx});mx pq.top().a;} cout time;return 0;
}
时间复杂度为:Ologn * time
二分法
猜时间对时间进行验证
// 二分答案 nlogn
#includeiostream
using namespace std;int n,a,b,w[500005];bool check(int t){int s0;for(int i1;in;i){if(w[i]t*a) continue;s(w[i]-t*ab-1)/b; //上取整}return st;
}
int main(){ios::sync_with_stdio(0);cinnab;for(int i1;in;i) cinw[i];int l0,r1e6,mid;while(l1r){midlr1;check(mid)?rmid:lmid;}coutrendl;
}
