NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組初賽
 E 排排站

作者 主題: E 排排站  (閱讀 416 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
E 排排站
« 於: 四月 19, 2015, 11:32:54 am »

好像在神人劉汝佳的書中有提到「鍵結結構-例題-移動小球」寫過一次,有移前及移後,
這題只是移後,應較簡單,程式要找一下再後補,找到了:
輸入第1行2個數字 ,球數n、指令數m ,指令兩種 A x y及B x y,將x移至y之前及之後
以下為移動小球的程式碼,而 NPSC 2004 國中 E排排站只有將 x  移至 y之後,應直接改一下即可
代碼: [選擇]
// 提升程式設計的邏輯思考力 p6-7~6-9 例6.2.1 移動小球 解法 B 鏈式串列
// 指令 A x y 將x移至y之前, B x y 將x移至y之後
#include <iostream>
using namespace std;
const int MaxN = 500000 ;  // 最多 50 萬 顆球
int lt[MaxN+1]; // 左 link
int rt[MaxN+1]; // 右 link
int n; // 小球 的數量

int main( )
{
int m; // 指令數 <= 100000
cin >> n >> m; // 輸入球數 、指令數
int  i ,f=1,r=n;
   lt[1]=-1; for(i=2; i<=n; ++i) lt[i]=i-1; // 左鍵
   rt[n]=-1; for(i=n-1; i>=1; --i) rt[i]=i+1; // 右鍵
   char c; // 指令
   int x,y; //移動的球號、目標的球號
   int a , b;
while( m-- )
{
cin >> c >> x >> y;
// 將 x 移出
a=lt[x] ; b=rt[x];   // x 的左a 及 右b
if(a<0) lt[b]=-1, f=b;
else if(b<0)  rt[a]=-1 , r=a;
else lt[b]=a , rt[a]=b;
// 將 x 插入 y 之左 或 之右
if( c == 'A' ) {  // 將 x 插入 y 之左
a=lt[y] ;
lt[x] = a; lt[y] = x;
rt[x] = y;
if(a==-1) f=x; else  rt[a] = x;
} else { // 將 x 插入 y 之右
b=rt[y];
lt[x] = y;
if(b==-1) r=x; else lt[b] = x;
rt[x] = b; rt[y] = x;
}
}
cout << f;
   while( rt[f]>0 )
   {
f = rt[f];
cout << " " << f ;
}
cout << endl;
 
   return 0;
}
/*
6 2
A 1 4
B 3 5
6 3
B 1 6
B 2 1
A 5 2
-----------
2 1 4 5 3 6
3 4 6 1 5 2
*/

« 上次編輯: 四月 19, 2015, 11:41:21 am 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組初賽
 E 排排站