worm

為什么我的眼里飽含淚水？因?yàn)槲页绦驔](méi)寫(xiě)完！

隨筆 - 5, 文章 - 2, 評(píng)論 - 10, 引用 - 0

數(shù)據(jù)加載中……

poj 3705解題思路及源代碼！

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

// Name : poj.cpp
3

// Author :
4

// Version :
5

// Copyright : Your copyright notice
6

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

,n,通過(guò)最少的“復(fù)制粘貼”數(shù)
7

// 變?yōu)槟嫘蛐蛄械膯?wèn)題。
8

//基本思想：如果n為奇數(shù)，假設(shè)n = 7；
9

// 1 2 3 4 5 6 7 將n左邊的最中間的兩個(gè)數(shù)依次移到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

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

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

//即可，結(jié)果為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 的情況，我因?yàn)橥丝紤]，wa了幾次，呵呵...

posted on 2009-03-06 08:36 WORM 閱讀(188) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

worm

poj 3705解題思路及源代碼！

導(dǎo)航

常用鏈接

留言簿(1)

隨筆檔案

文章檔案

相冊(cè)

OJ

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜