dd.java~4~

两台处理机A 和B处理n个作业。设第i个作业交给机器 A 处理时需要时间ai

package diaodu;

public class dd {
 public static void main(String[] args) {
   int sum;
   int a[]={2,5,7,10,5,2};
   int b[]={3,8,4,11,3,4};
   int []c=new int[6];
   sum=flowShop(a,b,c);

  }
  public static int flowShop(int []a,int []b,int c[])
  {int n=a.length;
    Element[]d=new Element[n];

    for(int i=0;i<n;i++)
    {
      int key=a[i]>b[i]?b[i]:a[i];
      boolean job=a[i]<=b[i];
      d[i]=new Element(key,i,job);
    }
    MergeSort.mergeSort(d);
    int j=0,k=n-1;
    for(int i=0;i<n;i++)
    {
      if(d[i].job) c[j++]=d[i].index;
      else c[k--]=d[i].index;
    }
    j=a[c[0]];
    k=j+b[c[0]];
    for(int i=1;i<n;i++)
    {
      j+=a[c[i]];
      k=j<k?k+b[c[i]]:j+b[c[i]];
    }
    return k;
  }
  public static class Element implements Comparable
{
 int key;
 int index;
 boolean job;

 private Element(int kk,int ii,boolean jj)
 {
   key=kk;
   index=ii;
   job=jj;
 }
 public int compareTO(Object x)
 {
   int xkey=((Element)x).key;
   if(key<xkey) return -1;
   if(key==xkey) return 0;
   return 1;
 }
}
}