作者Arim (Arim5566)
看板C_and_CPP
標題[ACM ] 101 TLE
時間Thu Mar 12 13:41:57 2009
怎麼改都是TLE..
以下是我的code..
#include<iostream>
using namespace std;
class Robort
{
public:
void init(int);
void MoveOnto(int,int);
void MoveOver(int,int);
void PileOnto(int,int);
void PileOver(int,int);
void PrintOut();
private:
int number;
int *data;
int *high;
int *blockhigh;
int i;
int j;
};
void Robort::init(int n)
{
number=n;
data=new int[number];
high=new int[number];
blockhigh=new int[number];
for(i=0;i<number;i++)
{
data[i]=i;
high[i]=0;
blockhigh[i]=0;
}
}
void Robort::MoveOnto(int a,int b)
{
if(data[a]!=data[b])
{
for(i=0;i<number;i++)
{
if(data[i]==data[a]&&high[i]>high[a])
{
data[i]=i;
blockhigh[data[i]]++;
blockhigh[data[a]]--;
high[i]=0;
}
else if(data[i]==data[b]&&high[i]>high[b])
{
data[i]=i;
blockhigh[data[i]]++;
blockhigh[data[b]]--;
high[i]=0;
}
}
blockhigh[data[a]]--;
data[a]=data[b];
blockhigh[data[b]]++;
high[a]=blockhigh[data[b]];
}
}
void Robort::MoveOver(int a,int b)
{
if(data[a]!=data[b])
{
for(i=0;i<number;i++)
{
if(data[i]==data[a]&&high[i]>high[a])
{
data[i]=i;
blockhigh[data[i]]++;
blockhigh[data[a]]--;
high[i]=0;
}
}
blockhigh[data[a]]--;
data[a]=data[b];
blockhigh[data[b]]++;
high[a]=blockhigh[data[b]];
}
}
void Robort::PileOnto(int a,int b)
{
int s=0,count=0,record=data[a],record1=high[a];
if(data[a]!=data[b])
{
for(i=0;i<number;i++)
{
if(data[i]==data[b]&&high[i]>high[b])
{
data[i]=i;
blockhigh[data[b]]--;
high[i]=0;
}
else if(data[i]==data[a]&&high[i]>=high[a])
{
count++;
}
}
i=0;
while(count>0)
{
if(i==number)
{
i=0;
}
if(data[i]==record&&high[i]==record1+s)
{
count--;
blockhigh[data[i]]--;
data[i]=data[b];
blockhigh[data[b]]++;
high[i]=blockhigh[data[b]];
s++;
}
i++;
}
}
}
void Robort::PileOver(int a,int b)
{
int count=0,record=data[a],record1=high[a],s=0;
count=0;
record=data[a];
if(data[a]!=data[b])
{
for(i=0;i<number;i++)
{
if(data[i]==data[a]&&high[i]>=high[a])
{
count++;
}
}
i=0;
while(count>0)
{
if(i==number)
{
i=0;
}
if(data[i]==record&&high[i]==record1+s)
{
count--;
blockhigh[data[i]]--;
data[i]=data[b];
blockhigh[data[b]]++;
high[i]=blockhigh[data[b]];
s++;
}
i++;
}
}
}
void Robort::PrintOut()
{
int count=0,s=0;
for(j=0;j<number;j++)
{
s=0;
count=0;
if(blockhigh[j]>0)
{
cout<<j<<": ";
for(i=0;i<number;i++)
{
if(data[i]==data[j])
{
count++;
}
}
while(count>0)
{
for(i=0;i<number;i++)
{
if(data[i]==data[j]&&high[i]==high[j]+s)
{
cout<<i<<' ';
count--;
s++;
}
}
i=0;
}
cout<<'\n';
}
else if(blockhigh[j]==0)
{
cout<<j<<": "<<j<<'\n';
}
else
{
cout<<j<<": "<<'\n';
}
}
}
int main()
{
char action1[5],action2[5];
int block1,block2,num;
Robort movepile;
cin>>num;
if(num>0&&num<25)
{
movepile.init(num);
while(cin>>action1)
{
if(!strcmp(action1,"quit"))
{
movepile.PrintOut();
cin>>num;
if(num>0&&num<25)
{
movepile.init(num);
continue;
}
else
{
break;
}
}
cin>>block1;
cin>>action2;
cin>>block2;
if(!strcmp(action1,"move"))
{
if(!strcmp(action2,"onto"))
{
movepile.MoveOnto(block1,block2);
}
else if(!strcmp(action2,"over"))
{
movepile.MoveOver(block1,block2);
}
}
if(!strcmp(action1,"pile"))
{
if(!strcmp(action2,"onto"))
{
movepile.PileOnto(block1,block2);
}
else if(!strcmp(action2,"over"))
{
movepile.PileOver(block1,block2);
}
}
}
}
return 0;
}
-------------------------------------------------------------------
我覺得是最後main那個while的問題...
因為我測試了一下ACM 100
如果是while(cin>>a>>b){...}跟 while(cin>>a){ cin>>b..}
在時間上面差了0.2秒
不過如果我是寫while(cin>>action1>>block1>>action2>>block2)
就沒辦法在輸入action1之後先判斷說是否為quit
懇請板上的大大為小弟解答@@ 謝謝
--
~宅男的四個徵兆~
∠□ ○ ！ * \○/ ★ (○ ？
╦╦└□ " ○□═ □ □>
║║√√ ╦══╦ ∥ |\
一回家就上PTT 每天想正妹 以當好人為樂 忘記正妹虧欠自己
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.138.236.174
1F：推 HudsonE:你的 count 有可能恆正, 就算運氣好沒有 TLE 也會 WA 03/12 16:18
2F：→ Arim:我count有歸零阿@@ 03/12 20:32
3F：→ Arim:而且我自己測試多筆資料 答案都正確@@ 03/12 20:34
4F：推 HudsonE:3 move 0 onto 1 pile 2 onto 1 move 2 onto 0 03/12 22:10
5F：→ HudsonE:pile 0 onto 1 quit 03/12 22:10
6F：→ Arim:謝謝 已解決 03/12 23:22