北大的ACM系统是怎么判time和memory的？－【附注】POJ 3414结题报告
两次AC，仅仅改变了数组的大小，时间竟然不一样，不由得开始怀疑ACM判题系统了
说一下POJ 3414吧。
看ACM解题分类，把这道题分到了广搜的范围内，感觉这道题目我并没有用到广搜呀，唯一有点相似的地方时，用了一个数组保存了路径而已，而这种做法根广搜是想趋甚远。
感觉做这种“倒水”题目就是一个技巧：先找准主杯
我是这么做的（做法很冗余，很丑陋）：分别把两个杯子各当一次主杯，算完后，看看哪一个步数少用哪一个。
具体的：当一个杯子为主杯后，先把之加满（FILL）,给辅杯倒水，如果辅杯水满，则优先把辅杯的水给倒掉（DROP）,两种情况之外就是 主杯给辅杯倒水了（POUR(I,J)）具体思路就是这样子的。
代码如下：
第一个是：＃define SIZE 200时候的 memory和time
第二个是: #define SIZE 100时候的memory和time
Source Code
| Problem: 3414 | User: omycle | |
| Memory: 252K | Time: 16MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <iostream>
using namespace std;
#define SIZE 100
int step=0;//记录多少步数
int duilie[SIZE];//记录中间的步骤
int step_1=0;
int duilie_1[SIZE];
int i=0;
int j=0;
int zhu=0;
int fu=0;
int zhu_1=0;
int fu_1=0;
int i_1=0;
int j_1=0;
//倒水
//1、fill(zhu)
//2、pour(zhu,fu)
//3、pour(zhu,fu)
//4、drop(fu)
void Play_1(const int a,const int b,const int c)
{
zhu_1=(a<b?a:b);
fu_1=(a>b?a:b);
if(zhu_1==a)
{
i_1=1;
j_1=2;
}
else
{
i_1=2;
j_1=1;
}
int zhu_1_c=0;
int fu_1_c=0;
//一种特殊情况：
//...
if(a==b)//第二种特殊情况
{
step_1=SIZE;
return;
}
while(zhu_1_c!=c&&fu_1_c!=c&&step_1<SIZE)
{
if(fu_1_c==fu_1)//如果辅杯的水满了，那么先把辅杯的水倒掉
{
fu_1_c=0;
duilie_1[step_1++]=3;
}
else if(zhu_1_c==0)//如果主杯的水为空，那么把主杯的水填满
{
zhu_1_c=zhu_1;//1--fill(i)
duilie_1[step_1++]=1;
}
else if(zhu_1_c!=0&&fu_1_c==0)
{//主杯有水，辅杯没水，那么
fu_1_c=zhu_1_c;//把主杯的水全部倒给辅杯，因为主杯水<辅杯水
zhu_1_c=0;
duilie_1[step_1++]=2;
}
else if(zhu_1_c!=0&&fu_1_c!=0)
{
if(zhu_1_c<=fu_1-fu_1_c)
{
fu_1_c+=zhu_1_c;
zhu_1_c=0;
}
if(zhu_1_c>fu_1-fu_1_c)//?存在问题
{
zhu_1_c=zhu_1_c-(fu_1-fu_1_c);
fu_1_c=fu_1;
}
duilie_1[step_1++]=2;
}
else
{
step_1=SIZE;
return ;
}
}
//退出循环，那么就开始把队列中的给输出了！！呵呵，笑一个
}
void dis_1()
{
printf("%d\n",step_1);
int i_step=0;
while(i_step<step_1)
{
switch(duilie_1[i_step++])
{
case 1:
printf("FILL(%d)\n",i_1);
break;
case 2:
printf("POUR(%d,%d)\n",i_1,j_1);
break;
case 3:
printf("DROP(%d)\n",j_1);
break;
}
}
}
void Play(const int a,const int b,const int c)
{
zhu=(a>b?a:b);
fu=(a<b?a:b);
if(zhu==a)
{
i=1;
j=2;
}
else
{
i=2;
j=1;
}
int zhu_c=0;
int fu_c=0;
//一种特殊情况：
/*
if(fu==c)
{
printf("1\n");
printf("FILL(%d)\n",j);
return;
}
*/
if(a==b)//第二种特殊情况
{
step=SIZE;
return;
}
while(zhu_c!=c&&fu_c!=c&&step<SIZE)
{
if(fu_c==fu)//如果辅杯的水满了，那么先把辅杯的水倒掉
{
fu_c=0;
duilie[step++]=3;
}
else if(zhu_c==0)//如果主杯的水为空，那么把主杯的水填满
{
zhu_c=zhu;//1--fill(i)
duilie[step++]=1;
}
else if(zhu_c!=0&&fu_c==0)
{
int temp=zhu_c;
if(temp<=fu)
{
fu_c=temp;
zhu_c=0;
}
else if(zhu_c>fu_c)
{
fu_c=fu;//满上辅杯
zhu_c=zhu_c-fu;
}
duilie[step++]=2;
}
else if(zhu_c==zhu&&fu_c<fu)//主杯满，辅杯不满，那么让辅杯满，主杯不满
{
int temp=fu-fu_c;
zhu_c=zhu_c-temp;
fu_c=fu;//
duilie[step++]=2;
}
else
{
//printf("impossible\n");
step=SIZE;
return ;
}
}
//退出循环，那么就开始把队列中的给输出了！！呵呵，笑一个
}
void dis()
{
printf("%d\n",step);
int i_step=0;
while(i_step<step)
{
switch(duilie[i_step++])
{
case 1:
printf("FILL(%d)\n",i);
break;
case 2:
printf("POUR(%d,%d)\n",i,j);
break;
case 3:
printf("DROP(%d)\n",j);
break;
}
}
}
int main()
{
int n,m,j;
cin>>n>>m>>j;
if(n==j)
{
printf("1\n");
printf("FILL(1)\n");
return 0;
}
if(m==j)
{
printf("1\n");
printf("FILL(2)\n");
return 0;
}
Play(n,m,j);
Play_1(n,m,j);
if(step==SIZE&&step_1==SIZE)
{
printf("impossible\n");
//step=SIZE;
return 0 ;
}
if(step<step_1)
{
dis();
//return;
}
else
dis_1();
return 0;
}
怎么判的....
回复删除