C++团建活动安排算法：最小化总费用

问题描述

又到了团建的时间，多多君负责安排这次的团建活动。多多君准备了三个活动（分别编号A、B和C），每个活动分别有人数上限以及每个人参加的费用。参加团建的有N个人（分别编号1～N），每个人先投票选择若干个意向的活动，最终每个人只能参加其中一个。

多多君收集完投票结果后，发现如何安排成为了大难题：如何在满足所有人的意向的情况下，使得活动的总费用最少。

于是多多君找到了擅长编程的你，希望你能帮助找到一个合理的团建计划。

输入描述

第一行，一个整数N，代表准备参加活动的人数（1<=N<=100）

接下来N行，每行一个由'ABC'组成的字符串，其中第1行表示第1个人投票了哪几个活动。

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int id; // 活动编号
    int max_num; // 最大人数
    int cost; // 活动费用
};

bool cmp(Activity a, Activity b) {
    return a.cost < b.cost; // 按费用从小到大排序
}

int main() {
    int n;
    cin >> n;
    vector<Activity> activities(3); // 三个活动
    activities[0] = {1, 0, 0}; // 活动A
    activities[1] = {2, 0, 0}; // 活动B
    activities[2] = {3, 0, 0}; // 活动C
    for (int i = 0; i < n; i++) {
        string vote;
        cin >> vote;
        for (char c : vote) {
            if (c == 'A') activities[0].max_num++;
            else if (c == 'B') activities[1].max_num++;
            else activities[2].max_num++;
        }
    }
    sort(activities.begin(), activities.end(), cmp); // 按费用排序
    int total_cost = 0;
    vector<int> result(n); // 存储每个人选的活动
    for (Activity activity : activities) {
        int num = min(activity.max_num, n); // 取最小值，防止人数超过n
        if (num == 0) continue; // 没有人选这个活动
        total_cost += activity.cost * num;
        for (int i = 0; i < n; i++) {
            if (activity.id == 1 && activities[1].max_num == 0 && activities[2].max_num == 0) { // 特殊情况，当只有活动A有人选时，选A
                result[i] = activity.id;
                activity.max_num--;
            } else if (activity.max_num > 0 && (result[i] == 0 || activities[result[i]-1].cost > activity.cost)) { // 更新每个人的选择
                result[i] = activity.id;
                activity.max_num--;
            }
        }
        if (activity.max_num > 0) { // 如果还有剩余的人数，继续选下一个活动
            activities[activity.id-1].max_num = activity.max_num;
        } else { // 如果已经选完了，退出循环
            break;
        }
    }
    cout << total_cost << endl;
    for (int i = 0; i < n; i++) {
        cout << (char)('A'+result[i]-1) << endl;
    }
    return 0;
}

算法解释

1. **读取输入数据：**读取参与人数N和每个人的投票信息。
2. 初始化活动信息： 创建一个Activity结构体数组，存储每个活动的ID、人数上限和费用。
3. 统计投票结果： 根据投票信息更新每个活动的人数上限。
4. 按费用排序： 对活动数组按照费用从小到大排序。
5. 分配活动： 循环遍历活动数组，依次分配活动：
   • 人数上限判断： 计算当前活动可分配的人数，并判断是否超过总人数N。
   • 分配给未分配人员： 从未分配人员中选择费用更高的活动进行替换，直到当前活动人数上限达到或所有人员分配完毕。
   • 剩余人数处理： 如果当前活动还有剩余人数，则将剩余人数重新分配到下一个活动。
6. 输出结果： 输出总费用和每个人的活动分配方案。

代码说明

• cmp 函数用于对活动数组进行按费用升序排序。
• result 数组存储每个人的活动分配方案。
• 循环遍历活动数组时，判断条件 result[i] == 0 || activities[result[i]-1].cost > activity.cost 用于判断是否需要替换当前人员的活动选择。
• 特殊情况 activity.id == 1 && activities[1].max_num == 0 && activities[2].max_num == 0 表示只有活动A有人选，此时优先分配活动A。

总结

该算法通过贪心策略，优先分配费用较低的活动，并根据活动人数上限进行调整，最终找到一个合理的团建活动安排方案，使得总费用最小。

相关主题

• 贪心算法
• 算法设计
• C++编程