#546. [ZJOI2010]任务安排
-
ID: 546
传统题
1000ms
128MiB
尝试: 1
已通过: 0
难度: 10
上传者:
zhangjiayi
标签> [ZJOI2010]任务安排
说明
小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的最小值。
输入输出样例
41 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
说明
样例说明
第一组数据中，唯一的工人首先执行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。
样例