题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1205
N个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为aii和bii。你可以安排每个作业的执行顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。求这个最少的时间。
Input第1行：1个数N，表示作业的数量。(2 <= N <= 50000)
第2 - N + 1行：每行两个数，中间用空格分隔，表示在M1和M2上加工所需的时间aii, bii。（1 <= aii, bii <= 10000)。Output输出完成所有作业所需的最少时间。Sample Input
4
3 7
2 1
1 1
4 2
Sample Output
14 分析：
思路：Johnson算法：
1：将任务分为两类，A类任务t1<t2，B类任务t1>=t2
2：两类任务分别排序，其中A类按 t1 递增排序，B类按 t2 递减排序
3：合并两类，将第二类任务接到第一类任务后面，此时任务的顺序最佳
4：遍历所有任务，计算总耗时 比如样例排序好之后是：
A:3 7
B:4 2
C:2 1
D:1 1
先在机器1完成A的3，然后在机器1进行B的4时，同时在机器2进行A的7，然后在机器1进行C的2，然后在机器1进行D的1，这段时间机器2都是
被A的7占领的，所以答案是：3+7+2+1+1=14 code：
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include<string.h>
using namespace std;
#define max_v 50005
struct node
{
int x,y;
}p[max_v],pp[max_v];
bool cmp1(node a,node b)
{
return a.x<b.x;
}
bool cmp2(node a,node b)
{
return a.y>b.y;
}
int f[max_v];
int main()
{
int n;
while(~scanf("%d",&n))
{
int len1=,len2=;
int x,y;
for(int i=;i<n;i++)
{
scanf("%d %d",&x,&y);
if(x<y)
{
p[len1].x=x;
p[len1++].y=y;
}else
{
pp[len2].x=x;
pp[len2++].y=y;
}
}
sort(p,p+len1,cmp1);
sort(pp,pp+len2,cmp2);
for(int i=len1;i<len1+len2;i++)
{
p[i]=pp[i-len1];
}
for(int i=;i<len1+len2;i++)
{
printf("%d %d\n",p[i].x,p[i].y);
}
printf("\n");
f[]=p[].x;
for(int i=;i<n;i++)
{
f[i]=f[i-]+p[i].x;
}
for(int i=;i<n;i++)
{
printf("%d ",f[i]);
}
printf("\n\n");
int sum=;
for(int i=;i<n;i++)
{
if(sum>=f[i])
{
sum+=p[i].y;
}else
{
sum=f[i]+p[i].y;
}
}
printf("%d\n",sum);
}
return ;
}