main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 144 行

/************************************************************************************

  57. 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单
 位：天）
            任务  │Ｊ1  Ｊ2  Ｊ3  Ｊ4  Ｊ5  Ｊ6
        ─────┼───────────────
          印刷车间│ ３  １２  ５   ２   ９  １１
          装订车间│ ８  １０  ９   ６   ３  １
 如何安排加工顺序，使加工时间最少。

  **********************************************************************************/

#include <stdio.h>

typedef struct
{
	int t1;
	int t2;
} Ti;

Ti ti[] = {{3,8},{12,10},{5,9},{2,6},{9,3},{11,1},{20,8}};

const int N = sizeof(ti)/sizeof(Ti);

int div(Ti ti[])
{
	Ti t;
	int i,j;
	int di = N;

	for(i=0; i<N; i++)
	{
		if(ti[i].t1-ti[i].t2 > 0)
		{
			for(j=i+1; j<N; j++)
			{
				if(ti[j].t1-ti[j].t2 < 0)
				{
					t = ti[i];
					ti[i] = ti[j];
					ti[j] = t;
					di = i;
					break;
				}
			}
			if(j == N)
			{
				di = i-1;
				break;
			}
		}
	}
	return di;
}

void sort1(Ti ti[], int s, int t)
{
	int i,j;
	Ti tmp;

	for(i=s+1; i<=t; i++)
	{
		tmp = ti[i];
		for(j=i-1; j>=0; j--)
		{
			if(ti[j].t1 > tmp.t1)
			{
				ti[j+1] = ti[j];
				continue;
			}
			break;
		}
		ti[j+1] = tmp;
	}
}

void sort2(Ti ti[], int s, int t)
{
	int i,j;
	Ti tmp;

	for(i=s+1; i<=t; i++)
	{
		tmp = ti[i];
		for(j=i-1; j>=0; j--)
		{
			if(ti[j].t2 < tmp.t2)
			{
				ti[j+1] = ti[j];
				continue;
			}
			break;
		}
		ti[j+1] = tmp;
	}
}

int calc(Ti ti[])
{
	int i;
	int ts = 0;
	int sum = 0;
	ts += ti[0].t1;
	for(i=1; i<=N; i++)
	{	
		if(ts > 0)
		{
			sum += ts;
			ts = 0;
		}
		sum += ti[i-1].t2;
		if( i == N ) break;
		ts += ti[i].t1 - ti[i-1].t2;
	}

	return sum;
}

void PrintTime()
{
	int i;
	for(i=0; i<N; i++)
		printf("%3d",ti[i].t1);
	printf("\n");
	for(i=0; i<N; i++)
		printf("%3d",ti[i].t2);
	printf("\n");
	printf("\n");
}

void main()
{
	int di;

	printf("排序前的序列:\n");
	PrintTime();
	di = div(ti);
	sort1(ti,0,di);
	sort2(ti,di+1,N-1);
	printf("排序后的序列:\n");
	PrintTime();
	printf("mincost=%d\n",calc(ti));
}