Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

郁闷啊,我用O(knlogn)的算法,怎么会超时啊,有谁能帮我看一下

Posted by bluewater at 2005-10-15 08:50:34 on Problem 1042
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Array
{
	int x;
	int s;
};
Array array[30];
int n,h;
int fi[30],di[30],ti[30];
int andy[30],sum[30];

int input( )
{
	int i;

	scanf("%d",&h);
	h *= 60;
	for(i = 0;i < n;i ++)
		scanf("%d",&fi[i]);
	for(i = 0;i < n;i ++)
		scanf("%d",&di[i]);
	ti[0] = 0;
	for(i = 1;i < n;i ++)
		scanf("%d",&ti[i]);

	return 0;
}
bool cmp(Array a,Array b)
{
	return (a.x < b.x || (a.x == b.x && a.s > b.s));
}
int compute(int limite,int len)
{
	int add,a,b;

	add = 0;
	make_heap(array,array + len,cmp);
	while(limite)
	{
		if(len == 0)
		{
			andy[0] += limite;
			return add;
		}
		pop_heap(array,array + len,cmp);
		a = array[-- len].x;
		b = array[len].s;
		add += a;
		andy[b] += 5;
		a -= di[b];
		if(a < 0) a = 0;
		limite -= 5;
		if(a == 0)
			continue;
		array[len].s = b;
		array[len ++].x = a;
		push_heap(array,array + len,cmp);
	}
	return add;
}
bool compare()
{
	int i;
	for(i = 0;i < n;i ++)
	{
		if(andy[i] < sum[i])
			return false;
		if(andy[i] > sum[i])
			return true;
	}
	return false;
}
int solution( )
{
	int j,i,limite,result,ttp;

	ttp = 0;

	limite = h;
	for(i = 0;i < n;i ++)
	{
		limite -= 5 * ti[i];
		for(j = 0;j <= n;j ++)
		{
			array[j].x = fi[j];
			array[j].s = j;
			andy[j] = 0;
		}
		result = compute(limite,i + 1);
		if(result > ttp)
		{
			ttp = result;
			for(j = 0;j < n;j ++) sum[j] = andy[j];
		}
		else if(result == ttp && compare())
			for(j = 0;j < n;j ++) sum[j] = andy[j];
	}
	printf("%d",sum[0]);
	for(i = 1;i < n;i ++)
		printf(", %d",sum[i]);
	printf("\n");
	printf("Number of fish expected: %d\n",ttp);
	return 0;
}
int main( )
{
	freopen("input.txt","r",stdin);
	freopen("out.txt","w",stdout);
	int i = 0;
	for(;;)
	{
		scanf("%d",&n);
		if(n == 0) break;
		if(i == 0) i = 1;
		else printf("\n");
		input( );
		solution( );
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator