C语言超级菜鸟 发表于 2012-12-26 21:14:14

请个位帮忙看下，如何减小如下代码的时间复杂度，谢谢。

这是我在BNUOJ新手题上遇到一个问题，取石子。（题目附于最后）
提交此题后用时1004ms（要求是1000ms以内），还望各位指教。
代码如下：
#include<stdio.h>
#define N 20
void main()
{
    int i,n,stu1,stu2;//stu1存n，stu2存m
    restart1:scanf("%d",&n);
if(n>20)
goto restart1;//n小于20
for(i=0;i<n;i++)
{
      restart2:scanf("%d%*c%d",&stu1,&stu2);
if(stu1<1||stu2>1000||stu2<1||stu2>=stu1)//限制范围
      goto restart2;
}
for(i=0;i<n;i++)
{
   if(stu1%(stu2+1)==0)
   printf("second\n");
else
   printf("first\n");
}
}
题目如下：
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

Input 输入数据首先包含一个正整数C(C ≤20)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1≤n,m≤1000），n和m的含义见题目描述。


Output 如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。


Sample Input 223 24 3

Sample Output firstsecond

Gw_love_VC. 发表于 2012-12-26 23:10:39

你好。。。我不太懂为什么定义了数组储存多组数据    但在后面的操作好像在用变量   {:5_94:}

小新110 发表于 2012-12-27 09:43:55

什么乱七八糟，看了半天没看懂，代码也是一团糟，文字也对不上。而且还用斜体，看了脖子都酸了。

风之残月 发表于 2012-12-27 13:22:42

建议代码写规范点

C语言超级菜鸟 发表于 2012-12-27 16:07:10

Gw_love_VC. 发表于 2012-12-26 23:10 static/image/common/back.gif
你好。。。我不太懂为什么定义了数组储存多组数据    但在后面的操作好像在用变量

复制过来出了问题……

C语言超级菜鸟 发表于 2012-12-27 16:07:45

小新110 发表于 2012-12-27 09:43 static/image/common/back.gif
什么乱七八糟，看了半天没看懂，代码也是一团糟，文字也对不上。而且还用斜体，看了脖子都酸了。

好吧，复制过来的，格式也变了……

C语言超级菜鸟 发表于 2012-12-27 16:08:33

风之残月 发表于 2012-12-27 13:22 static/image/common/back.gif
建议代码写规范点

我写的就是锯齿形的，不过复制过来就这样了……

C语言超级菜鸟 发表于 2012-12-27 16:10:21

Gw_love_VC. 发表于 2012-12-26 23:10 static/image/common/back.gif
你好。。。我不太懂为什么定义了数组储存多组数据    但在后面的操作好像在用变量

后面for循环那代码错了，可能是复制的时候出了点问题，应该是stu1%stu2==0

C语言超级菜鸟 发表于 2012-12-27 16:11:34

C语言超级菜鸟 发表于 2012-12-27 16:10 static/image/common/back.gif
后面for循环那代码错了，可能是复制的时候出了点问题，应该是stu1%stu2==0

额，少了一个东西。该是stu1%stu2+1==0 我这个脑子啊！

C语言超级菜鸟 发表于 2012-12-27 16:13:18

C语言超级菜鸟 发表于 2012-12-27 16:11 static/image/common/back.gif
额，少了一个东西。该是stu1%stu2+1==0 我这个脑子啊！

我不得不说这是输入的问题了，我写的是数组的元素，但他显示的是数组名，那个框框没了……

Gw_love_VC. 发表于 2012-12-28 21:09:14

C语言超级菜鸟 发表于 2012-12-27 16:07 static/image/common/back.gif
复制过来出了问题……

点击"<>"这个就可以复制代码了亲{:5_109:}

Gw_love_VC. 发表于 2012-12-29 19:00:21

楼主可以用一下位运算

wang_叻 发表于 2013-1-9 11:51:37

好复杂 。。。没玩过这个游戏= =想问下什么叫最优策略啊 ？

wang_叻 发表于 2013-1-9 12:33:14

本帖最后由 wang_叻 于 2013-1-9 12:35 编辑

额不知道 我想的 正确不正确啊   我说说吧 。。
这个 问题可能要倒着推   举两个例子
1    2    3    4    5    6    7    8    9    0
m=3   最后一个人（A）要赢，他前面的人（B）取时必须剩4个也就是在6，7号位置中间
为了让B一定能在6,7中间，B之前必须在2，3中间A可以让B在那里所以赢的是先取的;
1    2    34    5    6    7    8    9
m=2A要赢   B之前要在6，7中间， 为了让B在3，4中间 B之前必须在0，1之间。。。而B是先取 所以先取输==
（深绿色，绿色为赢方取的位置第一个是绿色时先取赢第一个无色后取赢）

根据上面可以找到算法
n%(m+1) !=0则先取赢
n%(m+1)==0则先取输



不知道对不对 ==先发这里了 有错误敬请指出啊！

迷失的农民 发表于 2013-1-11 21:38:23

复杂的代码，凌乱的代码真是看得人想死

阔怀 发表于 2015-8-30 12:04:47

看看
页: [1]
查看完整版本: 请个位帮忙看下，如何减小如下代码的时间复杂度，谢谢。