HDU-6000-Wash

ACM模版

描述

题解

给定 LL 件衣服让你去洗,洗衣房有 nn 个洗衣机和 mm 个烘干机,每个设备都给定你完成工作所需时间,但是由于设备比较烂,每个设备在某一段时间内只能洗一件衣服,问洗完这 LL 件衣服最短用时多久?

这个题很简单,想要时间最短,自然是考虑烘干最后一件衣服所需的时间,那么怎么要这个最后一件衣服在最短时间内处理完呢?这里就涉及到贪心了,首先我们可以根据洗衣机洗涤时间处理出来每件衣服洗干净的最早时间,然后呢,将最晚洗干净的衣服放进目前烘干这件衣服最早的烘干机,以此类推,这里很容易想到的是维护两个优先队列即可。

强调一点,在这里每台机器的完成工作所需的时间并不是贪心的决定性条件,因为考虑到机器的复用,所以我们需要根据最早完成这件工作的时间来贪心。洗涤和烘干两个过程都是如此贪心,不过为了时间最短,我们需要用洗涤最早和烘干最晚的搭配,用洗涤最晚和烘干最早的搭配……这样就能保证最后一件衣服用时最短。至于哪一件是最后烘干完成的,取最值即可。

代码

#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int L, n, m;
ll cost[MAXN];

struct node
{
    ll cost, base;

    bool operator < (const node &rhs) const
    {
        return cost > rhs.cost;
    }
};

ll x;
priority_queue<node> pqn1, pqn2;

int main()
{
    int T;
    scanf("%d", &T);

    for (int ce = 1; ce <= T; ce++)
    {
        while (!pqn1.empty())
        {
            pqn1.pop();
        }
        while (!pqn2.empty())
        {
            pqn2.pop();
        }

        scanf("%d%d%d", &L, &n, &m);
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &x);
            pqn1.push({x, x});
        }
        for (int i = 0; i < m; i++)
        {
            scanf("%lld", &x);
            pqn2.push({x, x});
        }

        node t;
        for (int i = 0; i < L; ++i)
        {
            t = pqn1.top();
            pqn1.pop();
            cost[i] = t.cost;
            t.cost += t.base;
            pqn1.push(t);
        }

        ll ans = 0;
        for (int i = L - 1; i >= 0; i--)
        {
            t = pqn2.top();
            pqn2.pop();
            ans = max(ans, t.cost + cost[i]);
            t.cost += t.base;
            pqn2.push(t);
        }

        printf("Case #%d: %lld\n", ce, ans);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WOLFRAM

Wolfram Language 快速编程入门

18620
来自专栏java学习

现在学习编程是学习JAVA好还是python好?

首先必须明确一点,Java和Python双方都有各自适合和发展的领域,所以别人常问我学习什么语言好,或者让我在两种语言进行比较好坏,编程语言只有适不适合,不存在...

19920
来自专栏落影的专栏

程序员进阶之算法练习(一)

前言 我对编程能力的认知包括三块: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)...

41360
来自专栏PPV课数据科学社区

【学习】1月份推荐给程序员们的技术书书单

时光飞逝,不知不觉,微信君已经和小伙伴们走过了2014,感谢你们的支持。小编会在2015年加倍努力,与你们一起分享好书。 2015年,首月,好多技术书的付印计划...

398100
来自专栏编程

新手如何学习UG,初学UG编程的快速…

新手如何学习UG,初学UG编程的有什么快速入门方法。也许你学习软件时不知道该从哪里着手学起。这里,远歌总结以往学习UG编程时的经验。告诉新手,学习时,一般先学习...

23190
来自专栏JAVA高级架构

同是3年开发经验,为什么你的技术比别人差很多?

你有没有静下心来思考过:同样是做了x年Java开发,为什么你的技术比别人差很多? 其实技术水平的高低和个人智商关系不大(毕竟能做Java编程开发大家都不会差),...

18510
来自专栏帘卷西风的专栏

游戏开发图书推荐--我读过的技术经典图书

很多同学问我学游戏开发应该看些什么书,我在这里抛砖引玉,给一份推荐表,希望大家共同提高。由于本人英文不太好,推荐的大部书籍都是国人编写的,有些经典的外文图书可...

13310
来自专栏陈树义

浅谈重构中踩过的坑

? 最近重构了公司一个将近10年的核心功能模块,踩了不少坑。在做这个重构的时候好几次都觉得做不下去,好几次压力都非常大,心想着我该不会做着做着就退出编程届了吧...

37070
来自专栏编程

C语言学不会,编程能力无法提升?你的问题我来解决!

C语言学不会,编程能力无法提升?这篇文章助你走上编程大牛之路。现在很多小伙伴都在学习C语言,C语言作为一门入门语言可以让你更加容易的了解计算机原理且C语言想单片...

27390
来自专栏钱曙光的专栏

为什么有些语言比别的快?

来自Ars Technica的文章评论了影响编程语言速度的各个方面。Ars这个网站虽然自称技术网站,但编程方面的文章一般比较浅,这篇也不例外。虽然文字很长,但无...

22050

扫码关注云+社区

领取腾讯云代金券