| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我用的是快速排序算法,我怀疑是输入的问题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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator