C++信息学奥赛

问题描述：有n个活动，每个活动有一个开始时间和结束时间。一个人只能参加一个活动，且活动时间不能重叠。请找出最多能参加的活动数量。

解题思路：

这是贪心算法的经典应用。最优策略是选择结束时间最早的活动，这样可以留下更多时间参加其他活动。

1. 将所有活动按结束时间从小到大排序
2. 选择第一个活动
3. 依次选择下一个活动，要求其开始时间不早于上一个选择的活动的结束时间
4. 重复步骤3，直到没有活动可选择

代码实现

// 活动选择问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 活动结构体
struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
    int index;  // 活动编号
    
    Activity(int s, int e, int i) : start(s), end(e), index(i) {}
};

// 比较函数：按结束时间排序
bool compare(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 选择最多的活动
vector<int> selectActivities(vector<Activity>& activities) {
    // 按结束时间排序
    sort(activities.begin(), activities.end(), compare);
    
    vector<int> selected;
    int lastEnd = -1;  // 上一个选中活动的结束时间
    
    // 遍历所有活动
    for (const auto& act : activities) {
        // 如果当前活动的开始时间晚于或等于上一个活动的结束时间
        if (act.start >= lastEnd) {
            selected.push_back(act.index);
            lastEnd = act.end;
        }
    }
    
    return selected;
}

int main() {
    // 示例输入
    vector<Activity> activities = {
        Activity(1, 4, 1),
        Activity(3, 5, 2),
        Activity(0, 6, 3),
        Activity(5, 7, 4),
        Activity(3, 9, 5),
        Activity(5, 9, 6),
        Activity(6, 10, 7),
        Activity(8, 11, 8),
        Activity(8, 12, 9),
        Activity(2, 14, 10),
        Activity(12, 16, 11)
    };
    
    vector<int> result = selectActivities(activities);
    
    cout << "最多可参加 " << result.size() << " 个活动，分别是：" << endl;
    for (int idx : result) {
        cout << "活动 " << idx << " ";
    }
    cout << endl;
    
    return 0;
}

问题描述：哈夫曼编码是一种用于数据压缩的前缀编码算法。给定一组字符及其出现频率，构造哈夫曼树并生成每个字符的哈夫曼编码，使总编码长度最小。

解题思路：

哈夫曼编码采用贪心策略，每次选择频率最低的两个节点合并成一个新节点，直到只剩下一个节点。

1. 将所有字符看作频率为其出现次数的节点
2. 创建一个优先队列（最小堆）存储这些节点
3. 从队列中取出频率最小的两个节点，合并成一个新节点，新节点的频率为两个节点的频率之和
4. 将新节点加入队列
5. 重复步骤3-4，直到队列中只剩下一个节点（根节点）
6. 从根节点出发，为每个字符生成编码（左子树为0，右子树为1）

代码实现

// 哈夫曼编码
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

// 哈夫曼树节点
struct HuffmanNode {
    char data;          // 字符
    int frequency;      // 频率
    HuffmanNode *left, *right;  // 左右子树
    
    HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列（最小堆）
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->frequency > b->frequency; // 频率小的节点优先级高
    }
};

// 生成哈夫曼编码
void generateCodes(HuffmanNode* root, string code, 
                  unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) return;
    
    // 如果是叶子节点，记录编码
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodes[root->data] = code;
        return;
    }
    
    // 左子树加"0"，右子树加"1"
    generateCodes(root->left, code + "0", huffmanCodes);
    generateCodes(root->right, code + "1", huffmanCodes);
}

// 构建哈夫曼树并返回编码
unordered_map<char, string> buildHuffmanTree(unordered_map<char, int>& frequencies) {
    // 创建最小堆
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap;
    
    // 将所有字符加入堆
    for (auto& pair : frequencies) {
        minHeap.push(new HuffmanNode(pair.first, pair.second));
    }
    
    // 构建哈夫曼树
    while (minHeap.size() > 1) {
        // 取出频率最小的两个节点
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        
        HuffmanNode* right = minHeap.top();
        minHeap.pop();
        
        // 创建新节点，频率为两个节点之和
        HuffmanNode* newNode = new HuffmanNode('$', left->frequency + right->frequency);
        newNode->left = left;
        newNode->right = right;
        
        // 将新节点加入堆
        minHeap.push(newNode);
    }
    
    // 生成哈夫曼编码
    unordered_map<char, string> huffmanCodes;
    generateCodes(minHeap.top(), "", huffmanCodes);
    
    return huffmanCodes;
}

int main() {
    // 示例：字符及其频率
    unordered_map<char, int> frequencies = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };
    
    // 构建哈夫曼树并获取编码
    unordered_map<char, string> huffmanCodes = buildHuffmanTree(frequencies);
    
    // 输出结果
    cout << "哈夫曼编码：" << endl;
    for (auto& pair : huffmanCodes) {
        cout << pair.first << " : " << pair.second << endl;
    }
    
    // 计算总编码长度
    int totalLength = 0;
    for (auto& pair : frequencies) {
        totalLength += pair.second * huffmanCodes[pair.first].length();
    }
    cout << "总编码长度: " << totalLength << endl;
    
    return 0;
}

问题描述：给定不同面额的硬币和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。假设每种硬币的数量是无限的。

解题思路：

当硬币面额满足"贪心选择性质"时（如人民币的面额），可以使用贪心算法：每次选择最大面额的硬币，直到总金额为0。

代码实现

// 最小硬币找零问题（贪心算法）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 贪心算法解决硬币找零问题
// 前提：硬币系统满足贪心选择性质（如人民币系统）
vector<int> minCoinsGreedy(vector<int>& coins, int amount) {
    vector<int> result;
    
    // 按面额从大到小排序
    sort(coins.rbegin(), coins.rend());
    
    for (int coin : coins) {
        // 尽可能使用当前面额的硬币
        while (amount >= coin) {
            amount -= coin;
            result.push_back(coin);
        }
        
        // 如果金额已凑够，退出循环
        if (amount == 0) break;
    }
    
    // 如果无法凑够金额，返回空向量
    if (amount != 0) {
        return {};
    }
    
    return result;
}

int main() {
    // 人民币硬币系统（满足贪心选择性质）
    vector<int> coins = {1, 5, 10, 20, 50, 100};
    int amount = 38;
    
    vector<int> solution = minCoinsGreedy(coins, amount);
    
    if (solution.empty()) {
        cout << "无法凑成金额 " << amount << endl;
    } else {
        cout << "凑成金额 " << amount << " 需要的最少硬币数为 " << solution.size() << endl;
        cout << "硬币组合：";
        for (int coin : solution) {
            cout << coin << " ";
        }
        cout << endl;
    }
    
    // 测试不满足贪心性质的情况
    vector<int> badCoins = {1, 3, 4};
    int badAmount = 6;
    vector<int> badSolution = minCoinsGreedy(badCoins, badAmount);
    
    cout << endl << "对于硬币系统 [1,3,4] 和金额 6：" << endl;
    if (badSolution.empty()) {
        cout << "无法凑成金额 6" << endl;
    } else {
        cout << "贪心算法得到的硬币数为 " << badSolution.size() << endl;
        cout << "贪心算法的硬币组合：";
        for (int coin : badSolution) {
            cout << coin << " ";
        }
        cout << endl;
        cout << "但最优解应为 2 枚（3+3）" << endl;
    }
    
    return 0;
}