题解：精灵与侏儒的对决

问题分析

这是一个环形座位分配问题，N个精灵要分配到N个环形排列的侏儒旁边的座位上。每个精灵有一个偏好的起始位置，如果该位置已被占用，就顺时针寻找第一个空位。

我们需要找到一种精灵的入场顺序，使得精灵赢得对决的次数最大化。

关键观察

1. 座位分配的确定性：无论精灵以什么顺序入场，最终的座位分配是唯一确定的（由偏好位置决定）
2. 问题转化：问题转化为在确定的座位分配下，如何通过重排精灵来最大化胜场数
3. 匹配问题：这实际上是一个最大匹配问题，我们需要将精灵与侏儒进行最优匹配

算法思路

步骤1：确定座位分配

首先模拟座位分配过程，确定每个侏儒最终会与哪个精灵配对：

vector<int> assignSeats(int n, vector<int>& A) {
    vector<int> seatToElf(n, -1);  // 每个座位对应的精灵编号
    vector<int> nextSeat(n);       // 下一个座位
    
    for (int i = 0; i < n; i++) {
        nextSeat[i] = (i + 1) % n;
    }
    
    for (int elf = 0; elf < n; elf++) {
        int start = A[elf] - 1;  // 偏好座位
        int current = start;
        
        // 寻找空位
        while (seatToElf[current] != -1) {
            current = nextSeat[current];
        }
        
        seatToElf[current] = elf;  // 分配座位
    }
    
    return seatToElf;
}

步骤2：贪心匹配

使用贪心策略进行最优匹配：

int maxWins(int n, vector<int>& dwarfPower, vector<int>& elfPower, vector<int>& assignment) {
    // 获取每个侏儒对应的精灵
    vector<int> dwarfToElf(n);
    for (int dwarf = 0; dwarf < n; dwarf++) {
        dwarfToElf[dwarf] = assignment[dwarf];
    }
    
    // 对精灵力量值排序（降序）
    vector<int> sortedElves = elfPower;
    sort(sortedElves.rbegin(), sortedElves.rend());
    
    // 对每个侏儒，找到能打败它的最强精灵
    int wins = 0;
    multiset<int> availableElves(sortedElves.begin(), sortedElves.end());
    
    vector<pair<int, int>> dwarfElfPairs;
    for (int dwarf = 0; dwarf < n; dwarf++) {
        dwarfElfPairs.emplace_back(dwarfPower[dwarf], elfPower[dwarfToElf[dwarf]]);
    }
    
    // 按侏儒力量值升序处理
    sort(dwarfElfPairs.begin(), dwarfElfPairs.end());
    
    for (auto& [dwarfPower, elfPower] : dwarfElfPairs) {
        // 找到能打败这个侏儒的最弱精灵
        auto it = availableElves.upper_bound(dwarfPower);
        if (it != availableElves.end()) {
            wins++;
            availableElves.erase(it);
        }
    }
    
    return wins;
}

复杂度分析

• 时间复杂度：O(N log N)，主要来自排序操作
• 空间复杂度：O(N)，用于存储中间结果

示例验证

以样例1为例：

N = 3
A = [2, 3, 3]
侏儒力量 = [4, 1, 10]  
精灵力量 = [2, 7, 3]

座位分配：精灵0→座位1，精灵1→座位2，精灵2→座位0
配对：侏儒1(力量1)-精灵0(力量2)，侏儒2(力量10)-精灵1(力量7)，侏儒0(力量4)-精灵2(力量3)

最优匹配：精灵1打败侏儒1，精灵0打败侏儒0，共2场胜利

总结

这个问题看似复杂，但通过分析可以发现：

1. 座位分配是确定的，与入场顺序无关
2. 问题本质是在固定配对关系下，通过重排精灵来最大化胜场
3. 使用贪心策略可以高效解决这个问题

关键技巧是将问题分解为两个独立的子问题：确定座位分配和最优匹配。