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

我用的是快速排序算法,我怀疑是输入的问题

Posted by butterflu at 2005-07-27 22:22:46
In Reply To:yes/my O(n^2) algorithm got accepted during the contest Posted by:frkstyc at 2005-07-27 22:17:54
#include<iostream.h>
#include<string.h>
const double c1=1.0/12;
const double c2=1.0/79;
double a[101];
bool b[101];
int t0[101],t1[10000];
int top=0,coq=0;
double solve(int t);
void Qsort(int a[],int b,int e);

main()
{
	int t;
	double u;
	char s[10];
	cout.setf(ios::fixed, ios::floatfield);
	cout.precision(1);
	cout.setf(ios::showpoint);

	while(	cin>>s && strlen(s) > 0)
	{
		if(s[0]=='Q')
			cin>>t1[coq++];
		else
		{
			cin>>t>>u;
			b[top]=(s[1] == 'h')? true:false;
			a[top]=u * ( b[top] ? 8 : 2 );
			t0[top]=t;
			top++;
		}
	}
//	Qsort(t1,0,coq-1);
	for(int i=0;i<coq;i++)
		cout<<t1[i]<<' '<<solve(t1[i])<<endl;
	return 0;
}

double solve(int t)
{
	double s=0,k;
	int i=0;
	for(i=0;i<top&&t0[i]<=t;i++)
	{
		if(b[i])
			k=a[i] - c1 * (t- t0[i]);
		else
			k=a[i]- c2 *(t- t0[i])*(t- t0[i]);
		if(k>0)
			s+=k;
	}
	if(s<1)
		s=1;
	return s;
}

void Qsort(int a[],int b,int e)
{
	int i=b,j=e,k;
	if(i==j)
		return;
	else
	{
		k=a[(i+j)/2];
		a[(i+j)/2]=a[i];
		while(i!=j)
		{
			while(i<j&&a[j]>=k)
				j--;
			if(i!=j)
			{
				a[i]=a[j];
				i++;
			}
			while(i<j&&a[i]<=k)
				i++;
			if(i!=j)
			{
				a[j]=a[i];
				j--;
			}
		}
		a[i]=k;
		if(b<i-1)
			Qsort(a,b,i-1);
		if(e>i+1)
			Qsort(a,i+1,e);
	}
}

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