poj 2751

这道题的大意是2台机器，n件任务，必须先在S1上做，再在S2上做。任务之间先做后做任意。求最早的完工时间。这是一个经典问题：2台机器的情况下有多项式算法（Johnson算法），3台或以上的机器是NP-hard的。思想就是贪心，时间复杂度是O(nlogn) 。
Johnson算法
(1) 把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。
(2) 对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。在这里，我一个数组搞定，把这两个集合分别向两边插入。

#include
#include
struct Point
{
 int key;
 int job;
 int index;
}p[10005];
int a[10005],b[10005],c[10005];
int cmp(const void *a,const void *b)
{
 return (*(struct Point*)a).key - (*(struct Point*)b).key;
}

int main()
{
 int n;
 int i,j,k;

 while(scanf("%d",&n)!=EOF)
 {
  if(n==0)
   break;
  for(i=0;i
  {
   scanf("%d%d",&a[i],&b[i]);
   p[i].key = a[i] > b[i] ? b[i] : a[i];
   p[i].job = a[i] <= b[i];
   p[i].index = i;
  }
  qsort(p,n,sizeof(p[0]),cmp);
  j = 0;
  k = n-1;
  for(i = 0;i < n;i++)
  {
   if(p[i].job)
    c[j++] = p[i].index;
   else
    c[k--] = p[i].index;
  }
  j = a[c[0]];
  k = j + b[c[0]];
  for(i = 1;i < n;i++)
  {
   j += a[c[i]];
   k = j < k ? k + b[c[i]] : j + b[c[i]];
  }
  printf("%d\n",k);
 }
 return 0;
}