C语言实现值班表生成算法：基于条件约束的优化策略

问题描述

给定一组大夫和一组条件约束，要求根据输入的条件确定唯一的值班表，且输入的n组条件中能够直接或间接得到任意两位大夫的关联关系。例如，条件 'A<C1' 表示：A大夫比C大夫晚1天值班；条件 'F=4' 表示：F大夫在星期四值班。

输入格式

首先输入一个整数n，表示条件的数量。
接下来输入n组条件，每组条件的格式有两种：
- 格式1：'编号比较运算符编号天数'，其中比较运算符有两种：'>' 或 '<'，分别表示“早”或“晚”。例如：'A<C1' 表示：A大夫比C大夫晚1天值班。
- 格式2：'编号 = 数值'，例如：'F=4' 表示：F大夫在星期四值班。

输出格式

输出周一至周日的值班序列。

输入样例

7
A<C1
D<E1
E>B2
B>G4
F<B1
F>C1
F=4

输出样例

EDBFCAG

算法1：暴力枚举

该算法通过枚举所有可能的排列组合，并判断是否满足所有条件。

**时间复杂度：**O(n^2)

C++ 代码

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

// 定义条件结构体
struct Condition {
    char doctor1;
    char doctor2;
    int days;
    char operator;
};

// 判断两个大夫的值班顺序是否满足条件
bool check(vector<char> &schedule, Condition &condition) {
    int index1 = find(schedule.begin(), schedule.end(), condition.doctor1) - schedule.begin();
    int index2 = find(schedule.begin(), schedule.end(), condition.doctor2) - schedule.begin();
    if (condition.operator == '<') {
        return index1 > index2 && abs(index1 - index2) <= condition.days;
    } else {
        return index1 < index2 && abs(index1 - index2) <= condition.days;
    }
}

// 判断一个值班序列是否满足所有条件
bool isValid(vector<char> &schedule, vector<Condition> &conditions) {
    for (auto &condition : conditions) {
        if (!check(schedule, condition)) {
            return false;
        }
    }
    return true;
}

// 生成所有可能的排列组合
void generatePermutations(vector<char> &doctors, vector<Condition> &conditions, int start, vector<char> &schedule, vector<vector<char>> &result) {
    if (start == doctors.size()) {
        if (isValid(schedule, conditions)) {
            result.push_back(schedule);
        }
        return;
    }
    for (int i = start; i < doctors.size(); i++) {
        swap(doctors[start], doctors[i]);
        schedule[start] = doctors[start];
        generatePermutations(doctors, conditions, start + 1, schedule, result);
        swap(doctors[start], doctors[i]);
    }
}

int main() {
    int n;
    cin >> n;
    vector<Condition> conditions(n);
    vector<char> doctors; // 存储所有大夫
    for (int i = 0; i < n; i++) {
        string conditionStr;
        cin >> conditionStr;
        if (conditionStr.find('=') != string::npos) { // 格式2
            conditions[i].doctor1 = conditionStr[0];
            conditions[i].days = stoi(conditionStr.substr(2));
            doctors.push_back(conditions[i].doctor1);
        } else { // 格式1
            conditions[i].doctor1 = conditionStr[0];
            conditions[i].doctor2 = conditionStr[2];
            conditions[i].days = stoi(conditionStr.substr(4));
            conditions[i].operator = conditionStr[1];
            doctors.push_back(conditions[i].doctor1);
            doctors.push_back(conditions[i].doctor2);
        }
    }
    // 去重
    sort(doctors.begin(), doctors.end());
    doctors.erase(unique(doctors.begin(), doctors.end()), doctors.end());
    vector<vector<char>> result;
    vector<char> schedule(doctors.size());
    generatePermutations(doctors, conditions, 0, schedule, result);
    if (result.size() == 1) {
        for (auto &doctor : result[0]) {
            cout << doctor;
        }
        cout << endl;
    } else {
        cout << "无法确定唯一的值班序列" << endl;
    }
    return 0;
}

算法2：优化策略

该算法通过分析条件约束，找到能够直接或间接确定值班序列的条件，并根据这些条件推导出唯一的值班序列。

**时间复杂度：**O(n^2)

C++ 代码

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

// 定义条件结构体
struct Condition {
    char doctor1;
    char doctor2;
    int days;
    char operator;
};

// 判断两个大夫的值班顺序是否满足条件
bool check(vector<char> &schedule, Condition &condition) {
    int index1 = find(schedule.begin(), schedule.end(), condition.doctor1) - schedule.begin();
    int index2 = find(schedule.begin(), schedule.end(), condition.doctor2) - schedule.begin();
    if (condition.operator == '<') {
        return index1 > index2 && abs(index1 - index2) <= condition.days;
    } else {
        return index1 < index2 && abs(index1 - index2) <= condition.days;
    }
}

// 判断一个值班序列是否满足所有条件
bool isValid(vector<char> &schedule, vector<Condition> &conditions) {
    for (auto &condition : conditions) {
        if (!check(schedule, condition)) {
            return false;
        }
    }
    return true;
}

// 优化算法：根据条件约束推导出唯一的值班序列
vector<char> generateSchedule(vector<Condition> &conditions) {
    vector<char> schedule(7); // 存储值班序列
    vector<char> doctors; // 存储所有大夫
    // 1. 提取所有大夫
    for (auto &condition : conditions) {
        doctors.push_back(condition.doctor1);
        if (condition.doctor2 != ' ') {
            doctors.push_back(condition.doctor2);
        }
    }
    // 2. 去重
    sort(doctors.begin(), doctors.end());
    doctors.erase(unique(doctors.begin(), doctors.end()), doctors.end());
    // 3. 根据条件约束推导出值班序列
    for (auto &condition : conditions) {
        if (condition.operator == '=') { // 格式2
            schedule[condition.days - 1] = condition.doctor1;
        } else { // 格式1
            // 找到第一个满足条件的排列组合
            for (int i = 0; i < 7; i++) {
                for (int j = i + 1; j < 7; j++) {
                    if (condition.operator == '<' && abs(i - j) <= condition.days) {
                        schedule[i] = condition.doctor1;
                        schedule[j] = condition.doctor2;
                    } else if (condition.operator == '>' && abs(i - j) <= condition.days) {
                        schedule[i] = condition.doctor2;
                        schedule[j] = condition.doctor1;
                    }
                }
            }
        }
    }
    // 4. 填充剩余的空位
    for (int i = 0; i < 7; i++) {
        if (schedule[i] == ' ') {
            for (auto &doctor : doctors) {
                if (find(schedule.begin(), schedule.end(), doctor) == schedule.end()) {
                    schedule[i] = doctor;
                    break;
                }
            }
        }
    }
    return schedule;
}

int main() {
    int n;
    cin >> n;
    vector<Condition> conditions(n);
    for (int i = 0; i < n; i++) {
        string conditionStr;
        cin >> conditionStr;
        if (conditionStr.find('=') != string::npos) { // 格式2
            conditions[i].doctor1 = conditionStr[0];
            conditions[i].days = stoi(conditionStr.substr(2));
        } else { // 格式1
            conditions[i].doctor1 = conditionStr[0];
            conditions[i].doctor2 = conditionStr[2];
            conditions[i].days = stoi(conditionStr.substr(4));
            conditions[i].operator = conditionStr[1];
        }
    }
    vector<char> schedule = generateSchedule(conditions);
    if (isValid(schedule, conditions)) {
        for (auto &doctor : schedule) {
            cout << doctor;
        }
        cout << endl;
    } else {
        cout << "无法确定唯一的值班序列" << endl;
    }
    return 0;
}

参考文献

值班表生成算法

总结

本文介绍了两种C语言实现值班表生成算法的方法：暴力枚举和优化策略。优化策略能够根据条件约束直接推导出唯一的值班序列，效率更高。实际应用中，可以根据具体需求选择合适的算法策略。