MACHINE - Lập lịch trên 3 máy
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
void quickSorttang(int A[],int X[],int b[], int lower,int upper)
{
int x = A[(lower + upper) / 2];
int i = lower;
int j = upper;
do{
while(A[i] < x)
i ++;
while (A[j] > x)
j --;
if (i <= j)
{
int tg=A[i];
A[i]=A[j];
A[j]=tg;
int tgx=X[i];
X[i]=X[j];
X[j]=tgx;
int tgb=b[i];
b[i]=b[j];
b[j]=tgb;
i ++;
j --;
}
}while(i <= j);
if (j > lower)
quickSorttang(A,X,b, lower, j);
if (i < upper)
quickSorttang(A,X,b, i, upper);
}
void quickSortgiam(int A[],int X[],int b[], int lower,int upper)
{
int x = A[(lower + upper) / 2];
int i = lower;
int j = upper;
do{
while(A[i] > x)
i ++;
while (A[j] < x)
j --;
if (i <= j)
{
int tg=A[i];
A[i]=A[j];
A[j]=tg;
int tgx=X[i];
X[i]=X[j];
X[j]=tgx;
int tgb=b[i];
b[i]=b[j];
b[j]=tgb;
i ++;
j --;
}
}while(i <= j);
if (j > lower)
quickSortgiam(A,X,b, lower, j);
if (i < upper)
quickSortgiam(A,X,b, i, upper);
}
main()
{
int n,a[10001],b[10001],a1[10001],b1[10001],a2[10001],b2[10001],x1[10001],x2[10001],u=0,v=0,d[10001],e[10001],f[10001];
long A[10001],B[10001],C[10001];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&d[i]);
for(int i=1;i<=n;i++)
scanf("%d",&e[i]);
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
for(int i=1;i<=n;i++)
{
a[i]=d[i]+e[i];
b[i]=e[i]+f[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]<=b[i])
{
u++;
a1[u]=a[i];
b1[u]=b[i];
x1[u]=i;
}
else
{
v++;
a2[v]=a[i];
b2[v]=b[i];
x2[v]=i;
}
}
quickSorttang(a1,x1,b1,1,u);
quickSortgiam(b2,x2,a2,1,v);
if(u>0)
{
A[1]=d[x1[1]];
B[1]=d[x1[1]]+e[x1[1]];
C[1]=d[x1[1]]+e[x1[1]]+f[x1[1]];
}
else
{
A[1]=d[x2[1]];
B[1]=d[x2[1]]+e[x2[1]];
C[1]=d[x2[1]]+e[x2[1]]+f[x2[1]];
}
for(int i=1;i<=u;i++)
{
A[i]=A[i-1]+d[x1[i]];
if(A[i]>B[i-1])
B[i]=A[i]+e[x1[i]];
else B[i]=B[i-1]+e[x1[i]];
if(B[i]>C[i-1])
C[i]=B[i]+f[x1[i]];
else C[i]=C[i-1]+f[x1[i]];
}
for(int i=u+1;i<=u+v;i++)
{
A[i]=A[i-1]+d[x2[i-u]];
if(A[i]>B[i-1])
B[i]=A[i]+e[x2[i-u]];
else B[i]=B[i-1]+e[x2[i-u]];
if(B[i]>C[i-1])
C[i]=B[i]+f[x2[i-u]];
else C[i]=C[i-1]+f[x2[i-u]];
}
printf("%ld\n",C[n]);
for(int i=1;i<=u;i++)
printf("%d ",x1[i]);
for(int i=1;i<=v;i++)
printf("%d ",x2[i]);
//getch();
}