求最短時間
描述:N個作業{1,2,………,n}要在由兩台機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工，然後在M2上加工。M1和M2加工作業i所需的時間分別為ai和bi，1≤i≤n。流水作業高度問題要求確定這n個作業的最優加工順序，使得從第一個作業在機器M1上開始加工，到最後一個作業在機器M2上加工完成所需的時間最少。
可以假定任何任務一旦開始加工，就不允許被中斷，直到該任務被完成，即非優先調度。
輸入:輸入包含若干個用例,第一行為一個正整數K(1<=K<=1000),表示用例個數,接下來K個用例,每個用例第一個為作業數N(1<=N<=1000)，接下來N行，每行兩個非負整數，分別表示在第一台機器和第二台機器上加工時間。
輸出:每個用例用一行輸出采用最優調度所用的總時間，即從第一台機器開始到第二台機器結束的時間。
樣例輸入:
1
4
5 6
12 2
4 14
8 7
樣例輸出:
33
[cpp]
#include <iostream>
#include <algorithm>//用於下面的排序函數sort()庫函數的調用
using namespace std;
class JOB
{
public:
int key,index;
bool job;
};
int cmp(JOB a,JOB b)
{
return a.key<b.key;
}
//算法的最主要的部分
int fun(int n,int a[],int b[],int c[])
{
int i,j,k;
JOB *d =new JOB[n];//開辟一個空間大小為n的JOB，即有n個的JOB對象
for(i=0;i<n;i++)
{
if(a[i]<b[i])
{
d[i].key = a[i];
d[i].job = true;
}
else
{
d[i].key = b[i];
d[i].job = false;
}
d[i].index = i;
}
sort(d,n+d,cmp);//對n個對象按key的大小進行排序
j=0;
k=n-1;
//下面的for()對上面對key進行排好的序再按job為真的key升排序，job
//為假降序排列，分別將它們的最先排的次序存到c[]數組中。
for(i=0;i<n;i++)
{
if(d[i].job == true)c[j++]=d[i].index ;
else c[k--]=d[i].index ;
}
j=a[c[0]];
k=j+b[c[0]];
//下面這個for()就是將最短的時間輸出
for(i=1;i<n;i++)
{
j=j+a[c[i]];
k= j<k ? k+b[c[i]] : j+b[c[i]];
//前一個作業的時間與前一個作業的第一個時間和第二個作業的時間相
//比,k為那個較大的
}
delete d;
return k;
}
//如下是主函數主要是用例的輸入和函數調用
int main()
{
int i,m,n,a[100],b[100],c[100];
cin>>m;
while(m--)
{
cin>>n;
for(i=0;i<n;i++)cin>>a[i]>>b[i];
cout<<fun(n,a,b,c)<<endl;
}
return 0;
}
求順序
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 128
void heap_adjust(int *array,int *index,int n,int loc)
{
int tmp,i,j,k;
tmp=array[loc];
k=index[loc];
for(i=loc;2*i<n;i=j)
{
j=2*i;
if(j+1<n && array[j]<array[j+1]) j++;
if(tmp < array[j]) {
array[i]=array[j];
index[i]=index[j];
}
else break;
}
array[i]=tmp;
index[i]=k;
}
void heap_sort(int *array,int *index,int n)
{
int i,j,tmp;
for(i=n/2;i>0;i--)
heap_adjust(array,index,n,i);
for(i=n;i>1;i--)
{
tmp=array[i];
array[i]=array[1];
array[1]=tmp;
j=index[i];
index[i]=index[1];
index[1]=j;
heap_adjust(array,index,i,1);
}
}
int main()
{
int n,i,j,k;
int A[MAX_LEN],B[MAX_LEN],C[MAX_LEN*2],D[MAX_LEN*2],E[MAX_LEN],F[MAX_LEN];
while(1==scanf("%d",&n)){
if(n > 0 && n < MAX_LEN){
for(i=1;i<=n;i++)
scanf("%d%d",A+i,B+i);
break;
}
printf("invalid n\n");
}
//initial tabs
for(i=1;i<=2*n;i++){
if(i<=n){
C[i]=A[i];
D[i]=i;
E[i]=0;
}
else{
C[i]=B[i-n];
D[i]=-(i-n);
}
}
//sort it!
heap_sort(C,D,2*n);
//dp find
for(k=1,i=1,j=n;i<=j;k++){
if(D[k] > 0){
if(E[D[k]] == 0){
F[i++]=D[k];
E[D[k]]=1;
}
}
else{
if(E[-D[k]] == 0){
F[j--]=-D[k];
E[-D[k]]=1;
}
}
}
printf("scheduled tasks:");
for(i=1;i<=n;i++)
printf("%-3d",F[i]);
printf("\n");
return 0;
}
