1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

思路:优先队列优化贪心

对于某一时刻,如果同时有三个作业,他们的完成时长为A < B < C.那么一定是先完成A 在完成 B 在完成 C。 这样加和是最小的。

所以对于任意时刻,我们查询优先队列里完成时长最小的作业进行完成即可。

P1877.第2题-多多做作业

    1000ms Tried: 131 Accepted: 16 Difficulty: 8 所属公司 : 拼多多
    算法与标签>贪心算法

多多有很多作业,同时刻他只能做一份作业。一个学期内多多共有 n 份作业,每份作业会在第 ti 时刻布置下来,需要 wi 时间才能完成,多多可以在任意时间改变自己当前的作业(前提是改变后的作业必须在布置且未完成),第 i 份作业的完成耗时为最终完成时刻减去作业被布置的时刻 ti;(详见样例)。问多多应如何分配自己的作业时间,才能使得所有作业的完成耗时总和最短?

输入描述

第一行为一个整数 n(1<=n<=105)n (1 <= n <= 10^5)n(1<=n<=105),表示有 n 份作业。

接下来 nnn 行,每行两个整数 ti,wi(1<=ti,wi<=109)ti, wi (1 <= ti, wi <= 10^9)ti,wi(1<=ti,wi<=109),分别表示作业的布置时刻与完成时间。

输出描述

输出一个整数,表示所有作业的最短完成耗时。

样例说明

对于 5050%50 的数据,1<=n<=1000,1<=ti,wi<=1051 <= n <= 1000, 1 <= ti, wi <= 10^51<=n<=1000,1<=ti,wi<=105;

对于 100% 的数据,1<=n<=105,1<=ti,wi<=1091 <= n <= 10^5,1 <= ti, wi <= 10^91<=n<=105,1<=ti,wi<=109;

数据保证对于任意i∈[1,n−1]i∈[1,n - 1]i∈[1,n−1],都有 ti≤ti+1t_i \leq t_{i+1}ti​≤ti+1​

样例1

输入

3
1 5
5 1
7 3

输出

10

说明

-在时刻1到时刻6之间做作业1,作业1开始时刻为1,完成时刻为6,耗时为6-1=5

-时刻6到时刻7做作业2,作业2开始时刻为5,完成时刻为7,耗时为7-5=2

-时刻7到时刻 10 做作业3,作业3开始时刻为7,完成时刻为10,耗时为3

总耗时为 5+2+3=1

样例2

输入

5
1 1
4 2
9 3
16 4
25 5

输出

15

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 226ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?