Aotle

你所看到的惊鸿，都曾被平庸磨练

Aotle

贪心算法的复习

哈夫曼编码

题目描述

给定一只含有小写字母的字符串；输出其哈夫曼编码的长度

输入

第一行一个整数T，代表样例的个数，接下来T行，每行一个字符串，0<T<=2000,字符串长度0<L<=1500.

输出

对于每个字符串，输出其哈夫曼编码长度

样例输入

1
2
3
4
3
hrvsh
lcxeasexdphiopd
mntflolfbtbpplahqolqykrqdnwdoq

样例输出

1
2
3
10
51
115

思路

哈夫曼编码的思路不难，主要讲一下优先级队列的使用。

在STL里有这个priority_queue，实现优先队列的结构，在优先队列中，优先级高的元素先出队列。

模板声明(3个参数)：priority_queue<Type, Container, Functional>

  • Type 为数据类型
  • Container 为保存数据的容器， 必须是用数组实现的容器，比如 vector、 deque 但不能用 list。默认用的是 vector
  • Functional 为元素比较方式，默认用 operator< , 即队头元素最大。

所以如果后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

如果要用到小顶堆，则一般要把模板的三个参数都带进去。STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆priority_queue<int, vector<int>, greater<int> >q;，即队头元素最小。对于自定义类型，则必须自己重载 operator< 或者自己写比较函数。

优先级队列的几个操作：

  • empty() 如果优先队列为空，则返回真
  • pop() 删除第一个元素
  • push() 插入一个元素
  • size() 返回优先队列中拥有的元素的个数
  • top()返回优先队列中有最高优先级的元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include<queue>
#include<string.h>
using namespace std;
int main()
  {
    int T;
    cin >> T;
    while (T--)
    {
        char s[1505];
        //存放每个字母的频率
        int n[26] = {0};
        cin >> s;
        for (int i = 0; i < strlen(s); i++)
        {
            n[s[i] - 'a']++;
        }
        //建立一个优先级队列
        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 0; i < 26; i++)
        {
            if (n[i] > 0)
                q.push(n[i]);
        }
        int sum = 0;
        //不断更新优先级队列
        while (q.size() >= 2)
        {
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            int temp = a + b;
            q.push(temp);
            sum += temp;
        }
        cout << sum << endl;
    }
    return 0;
  }

Homework

题目描述

临近开学了，大家都忙着收拾行李准 备返校，但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上：目前为止还未开动。

暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 5 张试卷，其中 4 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。

I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。

现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

输入

测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行，每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。

输出

对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位

提示：float 的精度可能不够，你应该使用 double 类型。

样例输入

1
2
3
4
5
6
4 20
4 10
5 22
10 3
1 2
0 0

样例输出

1
37.00

思路

背包类的贪心算法，计算物品性价比，按性价比从大到小排序，优先装入性价比大的，直到容量满为止。

0-1背包，物体不能拆分；背包，物体可以拆分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
struct zuoye
{
    double w;
    double v;
    double avg;
} z[25];
bool cmp(zuoye a, zuoye b)
{
    return a.avg > b.avg;
}
int main()
{
    int n, t;
    while (cin >> n >> t && (n || t)) //注意这里n,t不同时为0，但是可以个别为0
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> z[i].w >> z[i].v;
            z[i].avg = z[i].v / z[i].w;
        }
        sort(z, z + n, cmp);
        double sum = 0;
        for (int i = 0; i < n; ++i)
        {
            if (t >= z[i].w)
            {
                t = t - z[i].w;
                sum += z[i].v;
            }
            else
            {
                sum += t * z[i].avg;
                break;
            }
        }
        printf("%.2f\n", sum);
        //cout << setiosflags(ios::fixed) << setprecision(2) << sum << endl;
    }

    return 0;
}

问题 D: 海之征途——孙策

题目描述

孙策是王者峡谷里的坦克/战士。大船靠岸，江郡欢呼着迎来了他们的新领袖，人称江东小霸王的年轻人。游戏中，孙策的技能长帆破浪，可以驾船冲锋，可将船撞向敌方单位或者阻挡物，并造成一定的伤害。

现在，有一群好奇的江郡小朋友想跟着孙策一起出海航行，但孙策的船承载不了所有小朋友，所以孙策决定，尽可能带更多的小朋友出海，现在请你帮孙策谋一个策略，使得更多的小朋友有机会出海航行。已知的条件是孙策船的最大载重m，以及n个小朋友的体重。

输入

多组测试用例。
第一行输入包含一个整数T（1<=T<=1000），代表测试用例个数。

每组测试用例第一行有两个整数m和n。（0<=m<=1000， 0<=n<=1000），分别代表船的载重重量和小朋友的个数，接下来一行为n个小朋友的体重。

输出

每组测试用例对应一行输出，每行输出一个整数ans，代表最多能有ans个小朋友跟着一起出海。

样例输入

1
2
3
4
5
2
10 4
3 5 2 4
20 9
3 5 2 4 6 1 8 5 9

样例输出

1
2
3
6

提示

1.小朋友的体重可能相同 2.船可以满载

思路

贪心算法，先对小朋友按体重升序排列，然后体重小的优先上船，直到容量满为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int t, m, n;
int w[maxn];
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> m >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
        }
        sort(w, w + n);
        int ans = 0, c = m;
        for (int i = 0; i < n; i++)
        {
            if (w[i] <= c)
            {
                ans++;
                c -= w[i];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://aotle.top/2020/11/09/tanxin/

评论