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

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

这是我在BNUOJ新手题上遇到一个问题，取石子。（题目附于最后）
提交此题后用时1004ms（要求是1000ms以内），还望各位指教。
代码如下：
#include<stdio.h>
#define N 20
void main()
{
int i,n,stu1[N],stu2[N];//stu1[N]存n，stu2[N]存m
restart1:scanf("%d",&n);
if(n>20)
  goto restart1;//n小于20
for(i=0;i<n;i++)
{
      restart2:scanf("%d%*c%d",&stu1[i],&stu2[i]);
  if(stu1[i]<1||stu2[i]>1000||stu2[i]<1||stu2[i]>=stu1[i])//限制范围
   goto restart2;
}
for(i=0;i<n;i++)
{
   if(stu1[i]%(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

[/i][/i][/i][/i][/i][/i][/i][/i]

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

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

小新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

登录/注册后可看大图

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

复制过来出了问题……

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

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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

建议代码写规范点

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

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

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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

复制过来出了问题……

点击"<>"这个就可以复制代码了亲

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 3    4 5 6 7 8 9
m=2  A要赢 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

看看

账号		自动登录	找回密码
密码			立即注册