Posted on 2008-08-05 16:33
Hero 閱讀(138)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: job
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
double fmax( double a, double b )
{
if( a - b > 0 ) return a ;
else return b ;
}
double fmin( double a, double b )
{
if( a - b < 0 ) return a ;
else return b ;
}
int fmax( int a, int b )
{
if( a > b ) return a ;
else return b ;
}
int fmin( int a, int b )
{
if( a < b ) return a ;
else return b ;
}
int fpow( int a, int b )
{
int reval = 1 ;
for( int i=1; i<=b; i++ )
reval *= a ;
return reval ;
}
const int INF = 1000000 ;
const int size = 155 ;
int ina, inb, inn ;
int A[40], B[40] ;
int finishA[1100], finishB[1100] ;
int restartA[40], restartB[40] ;//機(jī)器A和B重新啟動的時間
void input()
{
scanf( "%d %d %d", &inn, &ina, &inb ) ;
for( int i=1; i<=ina; i++ ) {
scanf( "%d", &A[i] ) ; restartA[i] = 0 ;
}
for( int i=1; i<=inb; i++ ) {
scanf( "%d", &B[i] ) ; restartB[i] = 0 ;
}
}
void work()
{
int minval = INF ; int minnum = -1 ;
for( int i=1; i<=inn; i++ ) {
minval = INF ; minnum = -1 ;
for( int j=1; j<=ina; j++ ) {
if( minval > restartA[j] + A[j] ) {
minval = restartA[j] + A[j] ; minnum = j ;
}
}
restartA[minnum] = minval ; finishA[i] = minval ;
minval = INF ; minnum = -1 ;
for( int j=1; j<=inb; j++ ) {
if( minval > restartB[j] + B[j] ) {
minval = restartB[j] + B[j] ; minnum = j ;
}
}
restartB[minnum] = minval ; finishB[i] = minval ;
}
printf( "%d ", finishA[inn] ) ;
int maxval = -1 ;
for( int i=1; i<=inn; i++ ) {
if( maxval < finishA[i] + finishB[inn+1-i] )
maxval = finishA[i] + finishB[inn+1-i] ;
}
printf( "%d\n", maxval ) ;
}
int main()
{
freopen( "job.in", "r", stdin ) ;
freopen( "job.out","w",stdout ) ;
input() ;
//init() ;
work() ;
return 0 ;
}
Once these two calculations have been done and the arrays have been sorted, you end up with a picture like this:
Each line represents the activity of one job. Green and blue are "A" machines, and yellow, cyan, and purple are type "B" machines. A red line means that the job is in a container instead of a machine. The left portion corresponds to "A" jobs, where the end of each line is the time at which the kth job is completed. The right portion corresponds to "B" jobs, where the beginning of the line is the earliest that the kth job can be started with respect to the ending time of the all the "B" jobs. The white space in the middle represents the `slack' time, the time that the job sits in an intermediate container.
The best option is to match up the earliest completed "A" job with the "B" job that starts earliest, the second earliest completed "A" job with the second earliest started "B" job, etc. Take the maximum of these times. This corresponds to moving the the two representations together until they touch (one job has no 'slack' time).