题意分析

题目描述ACM竞赛需要将参赛学生分组，每组k人。要求每组中：

1. 每个学生姓名的长度与组内姓名平均长度的差值不超过2
2. 如果存在任何一组成员不满足条件，则整个分组方案失败

解题思路

1. 关键观察：

   • 每组k个姓名的长度必须相互接近（最大差值≤4）
   • 因为如果极端情况：最长和最短姓名差>4，则平均值必然与其中一个差值>2

2. 算法选择：

   • 将姓名按长度排序后，连续k个一组检查
   • 检查每组最大长度差是否≤4（数学推导保证此时必满足题目条件）
   • 这种方法比直接计算每组平均值更高效

3. 数学证明：

   • 设组内长度为a₁≤a₂≤...≤aₖ
   • 若aₖ - a₁ ≤4：
     • 平均值avg∈[a₁, aₖ]
     • |a₁ - avg| ≤ (aₖ - a₁) ≤2
     • |aₖ - avg| ≤ (aₖ - a₁) ≤2
     • 中间值自然满足

优化后的标程代码

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

bool canFormTeams(vector<int>& lengths, int k) {
    sort(lengths.begin(), lengths.end());
    for (int i = 0; i < lengths.size(); i += k) {
        if (lengths[i + k - 1] - lengths[i] > 4) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, caseNum = 0;
    while (cin >> n >> k, n || k) {
        vector<int> lengths(n);
        for (int i = 0; i < n; ++i) {
            string name;
            cin >> name;
            lengths[i] = name.size();
        }
        
        if (caseNum++) cout << "\n";
        cout << "Case " << caseNum << ": " 
             << (canFormTeams(lengths, k) ? "yes" : "no") << "\n";
    }
    
    return 0;
}

代码说明

1. 输入处理：

   • 使用快速IO优化（ios::sync_with_stdio）
   • 读取姓名并存储长度

2. 核心算法：

   • canFormTeams函数实现分组检查
   • 排序后检查每k个连续元素的极差

3. 输出处理：

   • 按要求格式输出结果
   • 测试用例间用空行分隔

4. 复杂度分析：

   • 时间复杂度：O(n log n)（排序主导）
   • 空间复杂度：O(n)

该方案通过数学观察将问题简化为极差检查，比直接计算每组平均值效率更高，能够处理最大规模输入（n=1000）。