博客声明

问题 B: 哈夫曼树

题目描述

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

输入

输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出

输出权值。

样例输入

2
2 8
3
5 11 30

样例输出

10
62

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    while(cin >> n)
    {
        int t[1010], sum = 0, i;
        for(i = 0; i < n; i++)
            cin >> t[i];
        for(i = 0; i < n - 1; i++)
        {
            sort(t + i, t + n);
            sum += t[i] + t[i + 1];
            t[i + 1] += t[i];
        }
        cout << sum << endl;
    }
    return 0;
}

问题 C: 算法10-2：折半插入排序

题目描述

折半插入排序同样是一种非常简单的排序方法，它的基本操作是在一个已经排好序的有序表中进行查找和插入。不难发现这个查找的过程可以十分自然的修改成折半查找的方式进行实现。
折半插入排序的算法可以描述如下：

在本题中，读入一串整数，将其使用以上描述的折半插入排序的方法从小到大排序，并输出。

输入

输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过1000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。

输出

只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。

样例输入

10
2 8 4 6 1 10 7 3 5 9

样例输出

1 2 3 4 5 6 7 8 9 10

提示

在本题中，需要按照题目描述中的算法完成折半插入排序的算法。与直接插入排序算法不同，折半插入排序算法在查找插入位置时采用了折半查找的方案，减少了关键字之间的比较次数，但是记录的移动次数并没有发生改变，因此折半插入排序的时间复杂度依旧为O(n2)，同样不是一种非常高效的排序方法。

代码

#include <iostream>
using namespace std;
int main()
{
    void BInsertSort(int array[], int num);
    int arr[1000];
    int tmp, n;
    cin >> n;
    for (tmp = 0; tmp < n; tmp++)
        cin >> arr[tmp];
    BInsertSort(arr, n);
    return 0;
}
void BInsertSort(int array[], int num)
{
    int i, tmp;
    for (int j = 0; j < num - 1; j++)
        for (i = 0; i < num - j - 1; i++)
            if (array[i] > array[i + 1])
            {
                tmp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = tmp;
            }
            for (i = 0; i < num; i++)
                cout << array[i] << " ";
            cout << endl;
}

问题 E: 最短路

题目描述

给一张无向图G(U, E), 询问任意两点的最短距离。

输入

第一行两个整数n，m表示图中结点数和边的数量, 结点从1到n编号。
接下来m行，每行三个整数u，v，w表示u，v之间有一条距离为w的边。
接下来一行一个整数q，表示询问次数。
接下来q行每行两个整数u，v，表示询问u到v的最短距离， 如果u不能到达v输出-1。
数据范围：n <= 100, m <= 5000, q <= 10000， 0 < w <= 1000。

输出

对应输出q行答案。

样例输入

5 10
1 2 1
2 5 10
1 3 2
1 4 4
1 5 6
2 3 4
2 4 3
3 4 1
3 5 4
4 5 2
5
1 4
3 5
2 3
4 2
5 2

样例输出

3
3
3
3
5

代码

#include <iostream>
using namespace std;
const int inf = 1e9;
int e[110][110];
int main()
{
    int n, m, u, v, w, q, i, j, k;
    cin >> n >> m;
    for (i = 0; i <= 110; i++)
    {
        for (j = 0; j <= 110; j++)
        {
            if (i == j)
                e[i][j] = 0;
            else
                e[i][j] = inf;
        }
    }
    for (i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        if (e[u][v] > w)
            e[u][v] = e[v][u] = w;
    }
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                if (e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];
                cin >> q;
                while (q--)
                {
                    cin >> u >> v;
                    if (e[u][v] != inf)
                        cout << e[u][v] << endl;
                    else cout << "-1" << endl;
                }
                return 0;
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。