2454.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"
#include"memory.h"
#include"algorithm"
#include"stdlib.h"

using namespace std;

typedef pair<int,int> city;

city c[180];
int n, k;


void init()
{
	int i;
	scanf( "%d", &n );
	k = n;
	n *= 3;

	for( i=0; i<n; i++ )
	{
		scanf( "%d", &c[i].first );
		c[i].second = i;
	}

	sort( c, c+n );
	
}

int a[60],b[60];


void search( int s1, int s2, int a[60], int b[60] , int s )
{
	int x, y, i, j;
	while( s1 <= s || s2 <= s )
	{
		i = rand()%k;
		j = rand()%k;
		x = c[a[i]].first;
		y = c[b[j]].first;

		s1 += y - x;
		s2 += x - y;
		swap( a[i], b[j] );
	}
}
	


void doit()
{
	int i,j,t,h,s1=0,s2=0;
	
	for( i=k; i<n; i++ )
	if( ( i - k ) % 2 == 0 )
	{
		s1 += c[i].first;
		a[ ( i - k ) / 2 ] = i;
	}
	else
	{
		s2 += c[i].first;
		b[ ( i - k ) / 2 ] = i;
	}

	if( s1 <= k*500 )
	search( s1, s2, a, b, k*500 );
	
	for( i=0; i<k; i++ )
	printf( "%d\n", c[a[i]].second+1 );
	
	for( i=0; i<k; i++ )
	printf( "%d\n", c[b[i]].second+1 );
	
	for( i=0; i<k; i++ )
	printf( "%d\n", c[i].second+1 );

}

int main()
{
	init();
	doit();

	return 0;
}