TWO - Lập lịch trên 2 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;
long A[10001],B[10001];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[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]=a1[1];
B[1]=a1[1]+b1[1];
}
else
{
A[1]=a2[1];
B[1]=a2[1]+b2[1];
}
for(int i=1;i<=u;i++)
{
A[i]=A[i-1]+a1[i];
if(A[i]>B[i-1])
B[i]=A[i]+b1[i];
else B[i]=B[i-1]+b1[i];
}
for(int i=u+1;i<=u+v;i++)
{
A[i]=A[i-1]+a2[i-u];
if(A[i]>B[i-1])
B[i]=A[i]+b2[i-u];
else B[i]=B[i-1]+b2[i-u];
}
printf("%ld\n",B[n]);
for(int i=1;i<=u;i++)
printf("%d ",x1[i]);
for(int i=1;i<=v;i++)
printf("%d ",x2[i]);
//getch();
}