P2608 [ZJOI2010]任务安排

    • 1通过
    • 18提交
  • 题目提供者 yyy2015c01 嘤嘤嘤
  • 评测方式 云端评测
  • 标签 各省省选 2010 浙江 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小Y最近遇到了一个棘手的问题。她有两项任务需要完成,其中第一项任务是重复操作1(op1)S1次,第二项任务是重复操作2(op2)S2次。为了完成这些任务,小 Y雇佣了N名工人。其中,第i个工人完成op1所需时间为T1,i,完成op2所需时间为T2,i。每个op1和op2都只能被一名工人完成,每名工人在任意时刻都只能做一项工作。

    所有的工人从第0秒开始工作。每当一个工人开始执行一项操作(op1或op2),他必须一直执行下去直到完成而不能被打断。我们记第一项任务完成的时间为E1,第二项任务完成的时间为E2,你的任务就是安排这些工人的工作,使得E1+E2最小。

    输入输出格式

    输入格式:

    输入文件的第一行包含一个整数T,表示输入文件中数据的组数。

    每个测试数据的第一行包含三个整数N S1 S2,含义如上文所述。

    接下来的N行每行包含两个整数T1,I、T2,i,分别表示第i个工人完成op1和op2所需的时间。

    输出格式:

    输出文件包含T行,每行只有一个整数,表示你找到的E1+E2的最小值。

    输入输出样例

    输入样例#1: 复制
    4
    
    1 2 3
    10 20
    
    3 5 7
    10 20
    15 16
    17 18
    
    4 3 6
    10 12
    8 9
    16 11
    13 20
    
    4 4 6
    7 12
    5 3
    6 5
    1000000 1000000
    
    输出样例#1: 复制
    100
    162
    84
    41
    

    说明

    样例说明

    第一组数据中,唯一的工人首先执行2次op1,在第20秒完成任务一(E1=20)。然后执行2次op2,在第80秒完成任务二(E2=80)。因此答案为20+80=100。

    第二组数据中,工人#1连续执行5次op1,在第50秒完成任务一(E1=50),工人#2执行7次op2,在第112秒完成任务二(E2=112)。因此答案为50+112=162。

    第三组数据和第二组数据类似。

    第四组数据中,工人#2首先连续执行6次op2¬,在第18秒完成任务二(E2=18)。于此同时,工人#3执行3次op1,同样在第18秒完成。此时还需要执行一次op1,因此让工人#2去执行最后一次op1,在第23秒完成任务一(E1=23)、因此答案为18+23=41。

    数据规模

    100%的数据中,1 ≤ T≤ 7,1 ≤ N ≤ 100,1 ≤ S1,S2≤ 7,1 ≤ T1,i T2,i�≤ 1000000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。