UVa 10665 Diatribe against Pigeonholes

本题要求为N个工人分配信箱，需满足包裹数越大的工人离书架中心越远的约束，并输出字母序最小的分配方案。核心在于设计贪心算法结合动态排序策略：使用双指针从两侧向中心分配，每次处理两个工人。采用两种排序方式——cmp1按包裹数降序、字母序升序选择左边工人，cmp2按包裹数降序、字母序降序选择右边工人。每次分配后重新排序剩余工人，确保在满足距离约束的前提下，左边放置字母序较小的工人，右边放置字母序较大的工

寂静山林

291人浏览 · 2025-12-02 17:03:46

寂静山林 · 2025-12-02 17:03:46 发布

问题描述

在一个无名小镇上，有一位木匠为一家公司制作了一个书架，但只用了两颗螺丝，导致书架中间比较脆弱。我们有 $N$ 个信箱（编号为 $\ldots, N$ ，其中 $1 < N < 26$ ），每个信箱对应公司的一名工人。每位工人用一个唯一的大写字母标识（从 A 开始，直到第 $N$ 个字母）。

为了保护脆弱的书架，我们需要按照以下规则为工人分配信箱：邮件最重的工人，其信箱应离书架中心最远。可以假设所有包裹重量相同，因此工人的"重量"由其收到的包裹数量决定。

输入格式

第一行：整数 $M$ ，表示测试用例的数量
每个测试用例：
- 第一行：整数 $N$ ，表示工人（信箱）数量
- 第二行：一个由大写字母组成的字符串，以 ‘#’ 结束，表示每个包裹对应的工人

输出格式

对于每个测试用例：

第一行：按信箱顺序输出对应的工人字母，用空格分隔
第二行：按相同顺序输出每个信箱中的包裹数量，用空格分隔

如果有多个分配方案满足要求，必须输出字母序最小的方案。

关键约束分析

包裹数优先原则：包裹数越大的工人，其信箱应离中心越远
字母序最小化：当有多个可行分配方案时，按位置顺序（位置1到位置N）输出工人字母时，字典序应最小
中心位置计算：书架中心位于位置 $(N + 1) /2$ （注意：这是分数中心，不是整数位置）
距离计算：位置 $i$ 到中心的距离为 $\times i - (N+1)|$ （乘以2避免浮点数）

解题思路

核心难点

问题的核心在于如何在满足"包裹数大的工人离中心更远"的约束下，找到字母序最小的分配方案。

算法设计

经过分析，我们可以采用一种贪心算法，结合动态排序策略：

1. 基本框架

使用两个指针：left 指向当前最左边的可用位置（靠近中心），right 指向当前最右边的可用位置（远离中心）
每次分配两个工人：一个给左边位置，一个给右边位置
左边位置放相对"轻"且字母序小的工人，右边位置放相对"重"且字母序大的工人

2. 排序策略

我们需要两种不同的排序方式：

cmp1：包裹数降序，包裹数相同时字母序升序

bool cmp1(pair<char, int> a, pair<char, int> b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}

cmp2：包裹数降序，包裹数相同时字母序降序

bool cmp2(pair<char, int> a, pair<char, int> b) {
    return a.second > b.second || (a.second == b.second && a.first > b.first);
}

3. 分配逻辑

对于每次迭代（处理两个工人）：

首先对剩余工人按 cmp1 排序，得到当前最优顺序
分情况处理：
- 情况 $1$ ：前两个工人包裹数不同
  - 如果第一个工人字母序小于第二个，则第一个放左边，第二个放右边
  - 否则交换后第一个放左边，第二个放右边
- 情况 $2$ ：前两个工人包裹数相同
  - 直接取第一个放左边，第二个放右边（通过 cmp2 重新排序确保右边得到字母序大的）
更新指针：left++, right--
重复直到所有工人分配完毕

4. 为什么需要动态排序？

每次分配后，剩余工人的相对优先级可能发生变化。例如，当包裹数相同的工人有多个时，分配的顺序会影响后续的选择。通过每次分配前重新排序，我们确保总是选择当前最优的工人。

5. 算法正确性证明

包裹数约束：通过 cmp1 和 cmp2 确保包裹数大的工人先被处理，分配到更远的位置
字母序最小：
- 左边位置总是分配字母序尽可能小的工人
- 右边位置在包裹数相同时分配字母序尽可能大的工人（避免小字母被"浪费"在右边）
- 通过动态排序和特殊情况处理，保证全局字母序最小
距离计算：使用 $\times i - (N+1)|$ 正确计算距离，处理奇偶 $N$ 的情况

时间复杂度分析

每次迭代需要对剩余工人排序，最坏情况下排序 $\log N)$
总共有 $O (N)$ 次迭代
总时间复杂度： $O(N^2 \log N)$
由于 $N < 26$ ，这个复杂度完全可行

代码实现

// Diatribe against Pigeonholes
// UVa ID: 10665
// Verdict: Accepted
// Submission Date: 2025-12-01
// UVa Run Time: 0.000s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

// 排序函数1：包裹数降序，包裹数相同时字母序升序
bool cmp1(const pair<char, int>& a, const pair<char, int>& b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
}

// 排序函数2：包裹数降序，包裹数相同时字母序降序
bool cmp2(const pair<char, int>& a, const pair<char, int>& b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first > b.first;
}

int main() {
    int M;
    cin >> M;
    
    while (M--) {
        int N;
        cin >> N;
        string s;
        cin >> s;
        
        // 统计包裹数
        vector<int> parcels(26, 0);
        for (char ch : s) {
            if (ch == '#') break;
            if (ch >= 'A' && ch <= 'Z' && ch - 'A' < N) 
                parcels[ch - 'A']++;
        }
        
        // 创建工人列表
        vector<pair<char, int>> workers(N);
        for (int i = 0; i < N; i++) 
            workers[i] = {'A' + i, parcels[i]};
        
        // 结果存储
        vector<pair<char, int>> result(N);
        int left = 0, right = N - 1;
        
        // 处理工人
        for (int i = 0; i < N; ) {
            if (i + 1 < N) {
                // 对剩余工人按cmp1排序
                sort(workers.begin() + i, workers.end(), cmp1);
                
                if (workers[i].second != workers[i + 1].second) {
                    // 包裹数不同
                    if (workers[i].first < workers[i + 1].first) {
                        result[left++] = workers[i];
                        // 对剩余工人按cmp2排序
                        sort(workers.begin() + i + 1, workers.end(), cmp2);
                        result[right--] = workers[i + 1];
                    } else {
                        swap(workers[i], workers[i + 1]);
                        result[left++] = workers[i];
                        sort(workers.begin() + i + 1, workers.end(), cmp2);
                        result[right--] = workers[i + 1];
                    }
                } else {
                    // 包裹数相同
                    result[left++] = workers[i];
                    sort(workers.begin() + i + 1, workers.end(), cmp2);
                    result[right--] = workers[i + 1];
                }
                i += 2;
            } else {
                // 只剩一个工人
                result[left] = workers[i];
                i++;
            }
        }
        
        // 输出工人字母
        for (int i = 0; i < N; i++) {
            if (i > 0) cout << " ";
            cout << result[i].first;
        }
        cout << endl;
        
        // 输出包裹数
        for (int i = 0; i < N; i++) {
            if (i > 0) cout << " ";
            cout << result[i].second;
        }
        cout << endl;
    }
    
    return 0;
}

示例分析

以题目中的第一个样例为例：

输入：
5
BDCECDCBCBCDECDABCEDVBCDBCDBCDABCAED#

处理过程：
1. 统计包裹数：A=3, B=8, C=11, D=9, E=4
2. 初始工人列表：A(3), B(8), C(11), D(9), E(4)
3. 排序后：C(11), D(9), B(8), E(4), A(3)
4. 分配过程：
   - 第一次：C放左边位置1，D放右边位置5
   - 第二次：B放左边位置2，E放右边位置4  
   - 第三次：A放中间位置3
5. 输出：C B A E D 和 11 8 3 4 9