hdu6000 Wash 思维、贪心

hdu6000

题意：有 L件衣服，n 个洗衣机，m 个烘干机。一台机器一次只能用于一件衣服，且每工作一次花费一定的时间。问洗完且烘干所有衣服最少要多久。

tags：好难想到。。

如果只用洗衣机那很好求，搞个优先队列就好。 但还要烘干，基本的思路是：对每件衣服，它的最终时间 = 它最小的洗衣时间 + 它最大的烘干时间 。 最后取所有衣服最终时间的最大值。

#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 200005, M = 1e6+10;int L, n, m; ll w[N], d[N], t[M]; struct P {ll a1, a2;bool friend operator < (P a, P b) {if(a.a1==b.a1) return a.a2>b.a2;return a.a1>b.a1;} }; priority_queue< P > q; int main() {int T; scanf("%d", &T);rep(cas, 1, T){while(!q.empty()) q.pop();scanf("%d%d%d", &L, &n, &m);rep(i,1,n) scanf("%lld", &w[i]), q.push((P){w[i],w[i]});rep(i,1,m) scanf("%lld", &d[i]);rep(i,1,L){P u = q.top(); q.pop();t[i] = u.a1;u.a1 = u.a1+u.a2;q.push(u);}while(!q.empty()) q.pop();rep(i,1,m) q.push((P){d[i],d[i]});ll ans = 0;per(i,L,1){P u = q.top(); q.pop();ans = max(ans, u.a1+t[i]);u.a1 = u.a1+u.a2;q.push(u);}printf("Case #%d: %lld\n", cas, ans);}return 0; }

转载于:https://www.cnblogs.com/sbfhy/p/7531702.html

总结

以上是生活随笔为你收集整理的hdu6000 Wash 思维、贪心的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。