Chinaunix首页 | 论坛 | 博客
  • 博客访问: 549889
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-11-27 17:04:47

/*Description 
John是个小列车站的站长,每次列车在这里重新编组时他就很烦恼。因为站上只有一个人字形的编组轨道,
所有的列车车厢都是从人字轨的右边依次进去,从左边出来。但有一些编组顺序John总编不出来,
John怀疑有些编组顺序是不可能完成的,可John又找不出那些是顺序是可以编组出,那些不可以。
请你写一个程序帮助John辨别哪些编组可以完成,哪些不能完成。


输入:

第一行是一个整数K,表示有多少个测试用例,以后每行一个测试用例,每行为n+1个整数,
第一个整数为n 表示有多少节车厢,后面n个整数表示需要编组成的顺序。比如说3节车厢,
按照1,2,3依次入轨编组,可以在左边形成1 2 3,1 3 2,2 1 3,2 3 1,321。

 

 
输出:

每行输出一个测试用例的结果。如果可以编组输出Yes,否则输出No。
 
  
Sample Input  
3 3 1 2 
4 1 2 3 4  
  
Sample Output  
No
Yes 

The last revised date:2011年5月3日21:50:12

Programmer:oracleason


*/


点击(此处)折叠或打开

  1. # include <stdio.h>

  2. int main()
  3. {
  4.     int input[110],stack[120],cases;

  5.     //printf("你要输入的测试用例个数:cases = ");
  6.     
  7.     scanf("%d",&cases);
  8.     
  9.     while(cases--)
  10.     {
  11.         int n;

  12.         //printf("输入这次测试的车厢个数:n = ");
  13.      scanf("%d",&n);
  14.         
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             scanf("%d",&input[i]);
  18.         }
  19.         
  20.         int top,p,current;
  21.         top = 0;
  22.         p = 1;
  23.         current = 1;
  24.         stack[0] = 0;

  25.         while(p<n+1)
  26.         {
  27.             stack[++top]=p;p++;
  28.             
  29.             while(stack[top]==input[current])
  30.             {
  31.                 top--;
  32.              current++;
  33.             }
  34.         }

  35.         //printf("%d\n",input[current]);
  36.         if( 0 == top)
  37.             printf("Yes\n");
  38.         else
  39.             printf("No\n");
  40.     }
  41.     return 0;
  42. }
/*总结
下面是没有对stack[0]初始化的输入输出
===========================================
你要输入的测试用例个数:cases = 3
输入这次测试的车厢个数:n = 4
4 3 2 1
-858993460
No
输入这次测试的车厢个数:n = 3
3 2 1
1
Yes
输入这次测试的车厢个数:n = 4
4 2 1 3
2
No
Press any key to continue

===========================================
你要输入的测试用例个数:cases = 4
输入这次测试的车厢个数:n = 4
4 3 2 1
Yes
输入这次测试的车厢个数:n = 3
3 1 2
No
输入这次测试的车厢个数:n = 4
4 2 1 3
No
输入这次测试的车厢个数:n = 4
4 2 1 3
No
Press any key to continue
=============================================

注意stack[0]的初始化 因为不初始化 那么数组的值都是相同的 
这样就影响到了while(stack[top]==input[current]) 的判断
值都是-858993460  还有第一次测试的数据初始化的stack数组元素中的值在第二次测试中
如果没有再次被初始化 那会保留第一次初始化值。。
*/




阅读(1624) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~