读书人

请教下关于程序提交超时的有关问题

发布时间: 2012-02-04 15:43:08 作者: rapoo

请问下关于程序提交超时的问题
最近在做ACM的题目,结果对了,每次提交都说超时,我到网上,我是用结构体存储数据的,我看到一个用全局的数组来存数据,结果他的能过。

下面是我的代码:

#include "iostream "

using namespace std;

struct Inf
{
intLNum;
intATime;
intInit[26];
intDec[26];
intDis[26];
};

struct Best
{
intEveTime[26];
intAll;
};

intMaxNum(intNum[],int n)
{
intMax=0;
int i=0;
while (i <n)
{
if (Num[Max] <Num[i])
Max=i;
i++;
}
returnMax;
}

int main(int argc, char *argv[])
{
InfDat;
InfTmp;
inti,j,k;//循环记录变量
intmark;
inttmp;
BestRes;
intLastTime;//除去走路,剩下的时间
BestMaxTmp;
cin> > tmp;
while (tmp!=0)
{
Dat.LNum=tmp;
cin> > Dat.ATime;
j=0;
while (j <Dat.LNum)
{
cin> > Dat.Init[j++];
}
j=0;
while (j <Dat.LNum)
{
cin> > Dat.Dec[j++];
}
j=0;
while (j <Dat.LNum-1)
{
cin> > Dat.Dis[j++];
}
//}
//mark=i;
//读数据成功,开始寻找最佳钓鱼最佳方案,贪心算法
//先找第一组的最佳方案
Res.All=-1;
for (i=1;i <=Dat.LNum;i++)
{
Tmp=Dat;
//在第一个至第i个湖钓鱼
LastTime=Tmp.ATime*12;
if (i> 1)
{
j=i-1;
while (j)
{
LastTime-=Tmp.Dis[j-1];
j--;
}
}
//j=0;//记录当前湖里最大收获湖的号码
MaxTmp.All=0;
for (k=0;k <16;k++)
{
MaxTmp.EveTime[k]=0;
}
while (LastTime)
{
j=MaxNum(Tmp.Init,i);
if (Tmp.Init[j]> 0)
{
MaxTmp.All+=Tmp.Init[j];
}
MaxTmp.EveTime[j]++;
Tmp.Init[j]-=Tmp.Dec[j];
if (Tmp.Init[j] <0)
{
Tmp.Init[j]=0;
}
LastTime--;
}
if (MaxTmp.All> Res.All)
{
Res=MaxTmp;
}
}
for (i=0;i <Dat.LNum-1;i++)
{
cout < <Res.EveTime[i]*5 < < ", ";
}
cout < <Res.EveTime[i]*5 < <endl;
cout < < "Number of fish expected: " < <Res.All < <endl;
cout < <endl;
cin> > tmp;
}
return 0;
}

这个是网上的代码:

#define max 200

int h,n;
int fi[max],di[max],ti[max];
int res[max],fish,resMax[max],fishMax;

int init();
void done();
void getFish(int ,int);

int main(int argc, char *argv[])
{
int i;

while(init()){
done();

for(i=1; i <n; i++){
printf( "%d, ",resMax[i]);
}
printf( "%d ",resMax[i]);
printf( "\n ");


printf( "Number of fish expected: %d\n\n ",fishMax);

}
return 0;
}

void getFish(int lack,int leftTime)
{
int i,j,pos;
int fi2[max];

fish=0;
for(i=1; i <=n; i++){
fi2[i]=fi[i];
res[i]=0;
}
while(leftTime> 0){
pos=1;
for(i=1; i <=lack; i++){
if(fi2[pos] <fi2[i]) {
pos=i;
}
}
if(fi2[pos]==0)break;
fish+=fi2[pos];
res[pos]+=5;
leftTime-=5;
if(fi2[pos]> di[pos]) fi2[pos]-=di[pos];
else fi2[pos]=0;
}
res[1]+=leftTime;
}

void done()
{
int i,j;
int leftTime=h;
for(i=1; i <=n; i++){
if(leftTime <=ti[i-1]*5){
break;
}
leftTime-=ti[i-1]*5;
getFish(i,leftTime);
if(fish> fishMax) {
fishMax=fish;
for(j=1; j <=n; j++){
resMax[j]=res[j];
}
}else if(fish==fishMax){


for(j=1; j <=n; j++){
if(resMax[j]> res[j]) break;
if(resMax[j] <res[j]){
for(;j <=n;j++){
resMax[j]=res[j];
}
break;
}
}
}
}

}

int init()
{
int i;
scanf( "%d ",&n);
if(n==0) return 0;
scanf( "%d ",&h);

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

请高手指点下,超时的原因?

[解决办法]
那就用全局的,
用空间换时间 ...

读书人网 >C++

热点推荐