来自NOCOW

[编辑] 题目说明

job在USACO上有Training以及Contest各一题，请大家注意区分。

[编辑] USACO Training

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 4 .2中的OI题目Job Processing的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] =问题分析

第一问直接贪心就行了。第二问可以直接按照对称的方法得到解。即a[i]对应b[n+1-i]。证明略。提示：利用单调性

楼上的分析太简略了不好理解。我们令delay[A][i]表示第i个A型机器的延时，显然，初始时所有delay[A]为0。然后对于所有的工件，我们选取delay[A][i]+machine[A][i](machine[A][i]表示第i个A型机器的加工用时）最小，也就是能在最快时间内完工的机器加工。更新delay[A][i]=delay[A][i]+machine[A][i]（这样这个机器就进入新的一轮加工中）。在此过程中，我们用cost[A][j]记录A操作加工出第j个零件的用时。用同样的方法求出delay[B][i]，cost[B][j]。

对于A操作的最短用时，显然就是cost[A]中的最大值。

因为我们在求解过程中是一个工件一个工件地送去加工，每次把一个工件送给用时最短的机器加工，那么显然有cost[A][1]<=cost[A][2]...<=cost[A][n]，同样适用于cost[B]。为了使B操作的用时最少，我们应该把A先加工出来的工件给B中加工最久的，即： cost[A][1]->cost[B][n],cost[A][2]->cost[B][n-1]......cost[A][i]->cost[B][n-i+1](Why?)(Because A的工序是与B首尾对应的，即A的第一个交给B的倒数第一个，即第n个，A的第i个交给B的倒数第i个，即第n-i+1个）那么 max(cost[A][i]+cost[B][n-i+1]) i=1,2,3,4...n就是B操作的最短用时。

补充，要是M1,M2很大，可以用堆去维护。

其实二分答案更为方便，分别对操作a和操作b的完成时间二分答案

看了各位大牛的解释之后，我是坐在马桶上冥思苦想，想到屁股出血，终于差不多想通了：注意到A产生的工件不一定是需要马上送给B来处理的。只要B可以在最后时限前处理好这些工件就行。那么我们反演时间，想象B的工作不是组装成品，而是逆时间轴运转，分解成品成为工件，那么cost[A]其实给出了B做拆解工作的时间约束。也就是说，假设B在T时间开始拆，那么最早拆完的那个工件在时间轴上要比A最晚交付的晚。依次，就可以得到上面的算法。 = = 太敬仰你们了。。。。交了代码之后发现usaco题解里面说的和我这里说的一样。。。匿了。。。

[编辑] 问题证明

by true(cai 教的)

现在来证明为什么在第一步最优的前提下能得出第二步最优: 假设在A已经最优的前提下,可以把一个零件拿出放到另一个A的机器上,使得B最后的结果比当前好,那么假设这两台A机器为A1,A2,对应的两台B机器为B1,B2.对应的时间有分别是a1,a2,b1,b2.且a2>=a1,b2>=b1,a2/2<=a1<=a2,b2/2<=b1<=b2. 那么原来A最优时的结果应该是max1{a1+b2,a2+b1},而现在如果把A的一个机器(假设是A2)的零件放到了A1上,那么现在的最优值就为 max2{a1+a2+b1,b2},现在只要证明max1恒<=max2就可以了,分四种情况证明: 一:

假设:
     a2+b1>=a1+b2,
     b2>=a1+a2+b1
     且b2<a2+b1.    
证明:
     由a2+b1>=a1+b2  =>   a2+b1>=b2  (1)
     由b2>=a1+a2+b1  =>   a2+b1<=b2  (2)
     综合(1)(2)可知  a2+b1=b2 与假设矛盾.

二:

假设:
     a2+b1>=a1+b2,
     a1+a2+b1>=b2
     且a1+a2+b1<a2+b1  <<=  显然不成立

三:

假设:
     a1+b2>=a2+b1, (1)
     b2>=a1+a2+b1
     且b2<a1+b2  (4)
证明：
   由b2>=a1+a2+b1  =>  b2-a1>=a2+b1  (2)
  （1）+（2）  =〉 b2>=a2+b1  (3)
   (3)(4)矛盾。

四：

假设：
      a1+b2>=a2+b1,   （1）
      a1+a2+b1>=b2    （2）
    且a1+a2+b1<a1+b2  （3）
证明：
     现在对不等式进行一种等价变换，在不影响(1)(2)不等式符号和a1+b2,a1+a2+b1的差的
     前提下,来试图证明不等式（3）是不可能的
    让a1=a2,则(1)==>>  a2+b2>=a2+b1
                (2)==>>  2a2+b1>=b2
                (3)==>>  2a2+b1<a2+b2
    
   观察(2),(3),应为a2>=0，所以显然是不可能同时成立的，所以问题得证。

即：

在A为最优的前提下一定能够造出一个问题二也是最优的解。

[编辑] 范例程序

[编辑] USACO Contest

Problem 2 工作安排 [Richard Peng, 2008]

Farmer John 有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1 <= N <= 100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个截止时间D_i(1 <= D_i <= 1000000000)，如果他可以完成这个工作，那么他可以获利P_i( 1<=P_i<=1000000000 ). 在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？答案可能会超过32位整型。

题目名称： job

输入格式

第1行：一个整数N.
第2~N+1行：第i+1行有两个用空格分开的整数：D_i和P_i.

样例输入 (job.in):

输出格式:

输出一行，里面有一个整数，表示最大获利值。

样例输出 (job.out):

样例解释：

第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润

USACO/job

目录