defrag.c

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

/*
  CTU Open Contest 2002
  =====================
  Sample solution for the problem: defrag

  Martin Kacer, Oct 2002
*/

#include <stdio.h>

#define MAXCLUS  100000

#define UNUSED  -1


/* where is the cluster that should be here at given position */
int whereis [MAXCLUS];

/* to where belongs the cluster that is at given position */
int belongs [MAXCLUS];

/* how many clusters are on the disk; how many are used */
int cntall, cntuse, cntfil;

/* number of move operations performed so far */
int moves;


/* read the file description and initialize structures */
void read_files (void)
{
	int n, x, fc = cntfil;
	cntuse = 0;
	for ( n = 0;  n < cntall;  ++n )
		belongs[n] = whereis[n] = UNUSED;
	while ( fc-- )
	{
		scanf ("%d", &n);
		while ( n-- )
		{
			scanf ("%d", &x);
			belongs[x-1] = cntuse;
			whereis[cntuse] = x-1;
			++cntuse;
		}
	}
}


/* simulate the moving operation */
void move_op (int src, int dst)
{
	/*printf ("%d %d\n", src+1, dst+1);*/
	whereis [belongs[dst] = belongs[src]] = dst;
	belongs[src] = UNUSED;
	++moves;
}


/* fill the unused cluster which has to be filled;
   if new one is freed, fill it too, recursively */
void fill_one (int idx)
{
	int n;
	while ( idx < cntuse && belongs[idx] == UNUSED )
	{
		n = whereis[idx];
		move_op (n, idx);
		idx = n;
	}
}


/* perform the defragmentation */
void defragment (void)
{
	int i;

	/* fill all of the unused clusters which are to be filled */
	for ( i = 0;  i < cntuse;  ++i )
		fill_one (i);

	/* now move away any cluster which is in a wrong place */
	for ( i = 0;  i < cntuse;  ++i )
		if ( i != belongs[i] )
		{
			move_op (i, cntuse);
			fill_one (i);
		}
}


int main (void)
{
	for ( ; ; )
	{
		scanf ("%d %d", &cntall, &cntfil);
		if ( !cntall )  break;
		read_files();
		moves = 0;
		defragment();
		if (moves == 0)
		 printf("No optimization needed.\n");
		else
		 printf ("We need %d move operations.\n", moves);
	}
	return 0;
}