2 shunfurh shunfurh 于 2017.09.18 02:59 提问

A Lazy Worker

Description

There is a worker who may lack the motivation to perform at his peak level of efficiency because he is lazy. He wants to minimize the amount of work he does (he is Lazy, but he is subject to a constraint that he must be busy when there is work that he can do.)

We consider a set of jobs 1, 2,..., n having processing times t1, t2,...,tn respectively. Job i arrives at time ai and has its deadline at time di. We assume that ti, ai, and di have nonnegative integral values. The jobs have hard deadlines, meaning that each job i can only be executed during its allowed interval Ii=[ai, di]. The jobs are executed by the worker, and the worker executes only one job at a time. Once a job is begun, it must be completed without interruptions. When a job is completed, another job must begin immediately, if one exists to be executed. Otherwise, the worker is idle and begins executing a job as soon as one arrives. You should note that for each job i, the length of Ii, di - ai, is greater than or equal to ti, but less than 2*ti.

Write a program that finds the minimized total amount of time executed by the worker.
Input

The input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. The number of jobs (0<=n<=100) is given in the first line of each test case, and the following n lines have each job's processing time(1<=ti<=20),arrival time(0<=ai<=250), and deadline time (1<=di<=250) as three integers.
Output

Print exactly one line for each test case. The output should contain the total amount of time spent working by the worker.
Sample Input

3
3
15 0 25
50 0 90
45 15 70
3
15 5 20
15 25 40
15 45 60
5
3 3 6
3 6 10
3 14 19
6 7 16
4 4 11
Sample Output

50
45
15

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.02 08:51
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 1337 A Lazy Worker
题意: 有一个懒工人,他要完成n个任务。每个任务都需要花费时间ti并且在[ai,bi]这个时间范围内完成。对于某个时间点如果有工作可以完成,那么他必须选择一个来完成,工作一旦开始就不能被打断。当然这个工人很懒,所以他希望他工作的时间越短越好。 解题思路: 首先我们可以预处理处对于某个时间点,工人可以完成的任务有哪些。当一个任务在时间点t满足 ai 这样预处理后就很容易想用DP来解决此问题
poj 1337 A Lazy Worker
这里用dp[ i ]表示时刻 i 及其之后的时间里所需工作的最少时间,那么从后向前递推即可, 一个重要条件是 di - ai #include #include #include #include #include using namespace std; vector t[300]; int dp[400]; int l[300], a[300], d
POJ1337---A Lazy Worker(dp)
Description There is a worker who may lack the motivation to perform at his peak level of efficiency because he is lazy. He wants to minimize the amount of work he does (he is Lazy, but he is subject
POJ 1337 A Lazy Worker 笔记
n个任务,完成任务 i 需要时间 ti ,任务到达时间 ai ,截止时间 bi。如果手上没活却有任务就必须干,接手的任务不能中途停止。多干不给钱,求最少干多少时间的活。
django python manage.py migrate遇到的错误
ValueError: The field admin.LogEntry.user was declared with a lazy reference to ‘xxx.user’, but app ‘xxx’ doesn’t provide model ‘user’. 的解决办法 今天数据库用django的模型建好表以后,运行python manage.py makemigrations 和p...
POJ 1337 A Lazy Worker(DP)
Description There is a worker who may lack the motivation to perform at his peak level of efficiency because he is lazy. He wants to minimize the amount of work he does (he is Lazy, but he is sub
A Lazy Worker - POJ 1337 dp
A Lazy Worker Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 1062   Accepted: 360 Description There is a worker who may lack the motivation to perform at
Fair-Play:The quick brown fox jumps over the lazy dog!
http://www.shiyanbar.com/ctf/1852  Fair-Play:  The quick brown fox jumps over the lazy dog!        ihxo{smzdodcikmodcismzd}       解: 背景和案例: 一种 Playfair密码变种加密方法如下:首先选择一个密钥单词(称为 pair)(字母不重复,
celery 详细教程-- Worker篇
Celery--Worker准备:安装pip install celery easy_install celery 使用Redis作为Broker时 ,需安装 celery-with-redis, 一般使用rabbitmq作为Broker开始:使用启动一个worker简洁--celery -A proj.task worker --loglevel=info解释: -A 是指对应的应用程序, 其参...
Flask基础 Part1
Flask 安装Flask模块 创建一个Flask项目 运行Flask 运行参数 在网页页面中进行控制台调试 Flask 安装Flask模块 pip install flask 创建一个Flask项目 创建一个app.py文件 from flask import Flask # 导入Flask包 app = Flask(__name__) # 获...