worm

為什么我的眼里飽含淚水？因為我程序沒寫完！

隨筆 - 5, 文章 - 2, 評論 - 10, 引用 - 0

數據加載中……

poj 3705解題思路及源代碼

//============================================================================
2

// Name : poj.cpp
3

// Author :
4

// Version :
5

// Copyright : Your copyright notice
6

// Description : 題目大意就是將正序數列1,2,3,

,n,通過最少的“復制粘貼”數
7

// 變為逆序序列的問題。
8

//基本思想：如果n為奇數，假設n = 7；
9

// 1 2 3 4 5 6 7 將n左邊的最中間的兩個數依次移到7的右邊
10

// 1 2 5 6 7 3 4 的最中間
11

// 1 6 7 3 2 5 4
12

// 7 3 2 1 6 5 4 將 3 2 1與 6 5 4 交換
13

// 7 6 5 4 3 2 1
14

//總的次數為(n+1)/2;
15

// n = 偶數時，可以先把n不管，這樣n-1就為奇數的情況，求出后的序列在和n交換一下
16

//即可，結果為n/2 + 1;
17

//============================================================================
18

#include <iostream>
20

using namespace std;
21

void solve(int n) {
22

int x = (n+1)/2 - 1;
23

int y = n;
24

for (int i = 0; i < x; ++i) {
25

cout << n/2 << " " << 2 << " " << y-2-i << endl;
26

n -= 2;
27

}
28

cout <<"2 " << x << " " << x + 1 << endl;
29

}
30

int main() {
32

int n;
33

cin >> n;
34

if (n == 1) {
35

cout << 0 <<endl;
36

return 0;
37

}
38

if (n == 2) {
39

cout << "1" <<endl;
40

cout << "1 1 1" <<endl;
41

return 0;
42

}
43

if (n % 2 != 0) {
44

cout << (n+1)/2 <<endl;
45

solve(n);
46

}
47

else {
48

cout << n/2 + 1 << endl;
49

solve(n-1);
50

cout << 1 << " "<< n-1 <<" 1" <<endl;
51

}
52

return 0;
54

}
55

最后一定要注意1 和 2 的情況，我因為忘了考慮，wa了幾次，呵呵...

posted on 2009-03-06 08:52 WORM 閱讀(317) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

worm

poj 3705解題思路及源代碼

導航

常用鏈接

留言簿(1)

隨筆檔案

文章檔案

相冊

OJ

搜索

最新評論

閱讀排行榜

評論排行榜