worm

为什么我的眼里饱含泪水？因为我程序没写完！
随笔 - 5, 文章 - 2, 评论 - 10, 引用 - 0
数据加载中……

poj 3705解题思路及源代码

 1//============================================================================
 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
19#include <iostream>
20using namespace std;
21void 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
31int 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
53    return 0;
54}
55

最后一定要注意1 和 2 的情况，我因为忘了考虑，wa了几次，呵呵...

posted on 2009-03-06 08:52 WORM 阅读(305) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理