题意分析

这道题要求判断在理发店服务流程中，对于给定的周期性顾客到达序列，是否可以通过添加有限且相邻的等待时间单位，满足以下条件：

1. 每个顾客到达时立即开始服务（不会离开）
2. 避免理发师Tom同时服务多个顾客的冲突（学徒的服务可并行）
3. 服务流程顺序保持不变：换衣(Change)-洗头(Wash)-理发(Cut)-洗头(Wash)-吹干(Dry)-换衣(Change)-付款(Pay)

关键点：

• 顾客到达时间由输入序列循环累加生成：第一个顾客在时间1，第n个顾客的到达时间 = 1 + 周期和×完整周期数 + 当前周期内的前缀和
• 需要为所有顾客插入相同的等待时间序列（位置和数量固定）
• 添加的等待时间必须是有限的

解题思路

1. 计算周期总和T：对输入序列的间隔求和
2. 生成前缀和数组：
   • 第1个顾客前缀和为0
   • 第(i+1)个顾客前缀和 = 前i个间隔之和（共k-1个前缀和）
3. 计算所有可能的差集D：
   • 遍历前缀和数组，计算所有两两组合的差（s[i] - s[j]）
4. 检查模T余数覆盖情况：
   • 计算D中每个元素对T的余数（映射到[0, T-1]）
   • 检查余数是否完全覆盖[0, T-1]区间
5. 判断结果：
   • 如果余数覆盖了整个[0, T-1]区间，输出"No"（无法避免冲突）
   • 否则输出"Yes"（存在可行解）

算法分析

• 时间复杂度：对于k个间隔，计算差集和余数检查的时间为O(k² + T)，其中k≤20，T≤400，可以高效执行
• 空间复杂度：主要消耗在存储差集和余数数组，O(k² + T)
• 数学原理：当余数覆盖满[0, T-1]时，Tom的服务步骤时间点与顾客到达时间的差值必然冲突，否则可以调整等待时间避免冲突

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

// 解析输入字符串
vector<int> parseInput(string str) {
    // 去除空格
    str.erase(remove_if(str.begin(), str.end(), ::isspace), str.end());
    
    if (str == "(0)") {
        return vector<int>();
    }
    
    vector<int> res;
    string nums = str.substr(1, str.size() - 2);
    size_t pos = 0;
    string token;
    
    while ((pos = nums.find(',')) != string::npos) {
        token = nums.substr(0, pos);
        res.push_back(stoi(token));
        nums.erase(0, pos + 1);
    }
    
    if (!nums.empty()) {
        res.push_back(stoi(nums));
    }
    
    return res;
}

int main() {
    string line;
    while (getline(cin, line)) {
        vector<int> a = parseInput(line);
        
        // 终止条件
        if (a.empty() || (a.size() == 1 && a[0] == 0)) {
            break;
        }
        
        int k = a.size();
        int T = 0;
        // 计算周期总和 T
        for (int num : a) {
            T += num;
        }
        
        // 生成前缀和数组 s
        vector<int> s;
        s.push_back(0);       // 顾客1的前缀和是0
        if (k > 1) {
            s.push_back(a[0]); // 顾客2的前缀和是 a0
            for (int i = 1; i < k - 1; i++) {
                s.push_back(s.back() + a[i]);
            }
        }
        // 如果 k 为 1，那么只有第一个顾客（s 只包含 0）

        // 计算差集 D（所有前缀和之间的差值）
        set<int> D;
        for (int i = 0; i < s.size(); i++) {
            for (int j = 0; j < s.size(); j++) {
                D.insert(s[i] - s[j]);
            }
        }

        // 检查余数覆盖情况
        vector<bool> residues(T, false);
        for (auto d : D) {
            int r = (d % T + T) % T;  // 调整为非负余数
            residues[r] = true;
        }

        // 检查 [0, T-1] 是否被完全覆盖
        bool fullCoverage = true;
        for (int i = 0; i < T; i++) {
            if (!residues[i]) {
                fullCoverage = false;
                break;
            }
        }

        // 输出结果
        cout << (fullCoverage ? "No" : "Yes") << endl;
    }
    return 0;
}

代码说明

1. 输入处理：parseInput函数去除空格和括号，提取间隔序列
2. 核心计算：
   • 循环计算顾客到达时间的周期特性（周期和T，前缀和数组s）
   • 通过两重循环计算所有差值的余数分布
3. 覆盖检查：
   • 使用布尔数组标记存在的余数
   • 检查[0, T-1]区间是否被完全覆盖
4. 结果判断：
   • 完全覆盖 → "No"（无法避免冲突）
   • 未完全覆盖 → "Yes"（存在可行解）