「eJOI2022」Adjacent Pairs 题解

算法思路

本题使用贪心策略和频率统计来解决数组变换问题。核心思想是通过统计奇偶位置的数值频率，找到最优的两个数值组合来最小化操作次数。

关键观察

1. 问题分析

最终数组只包含两个不同的值，且需要保持相邻元素不同的性质。考虑两种模式：

• 模式1：奇偶位置使用不同的值
• 模式2：奇偶位置可以使用相同的值，但需要满足相邻约束

2. 操作次数计算

最小操作次数 = 总元素数 - 保留的元素数 需要最大化保留的元素数

代码解析

数据结构初始化

int o[200010], e[200010], a[200010], vis[200010];
basic_string<int> del[200010], del2[200010];
unordered_map<int, int> mp[200010];
multiset<int> sto, ste;

• o[i]: 数值 $i$ 在奇数位置的出现次数
• e[i]: 数值 $i$ 在偶数位置的出现次数
• mp[i][j]: 记录模式 $(i,j)$ 的有效段数

频率统计

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (i & 1) o[a[i]]++;
    else e[a[i]]++;
}

模式识别与统计

for (int i = 1; i < n; i++) {
    if (c(i) != lst) 
        mp[lst.first][lst.second] += (k + 1) >> 1, k = 1, lst = c(i);
    else k++;
}
mp[lst.first][lst.second] += (k + 1) >> 1;

统计所有连续相同模式 $(x,y)$ 的段数，其中模式表示奇偶位置的数值组合。

第一种情况：奇偶位置不同值

for (int i = 1; i <= n; i++) {
    for (auto [j, x] : mp[i]) {
        ans1 = min(ans1, -e[i] - o[j] + x);
    }
}

计算使用不同数值 $i$（偶数位）和 $j$（奇数位）时的最小操作次数。

第二种情况：复杂模式匹配

for (int i = 1; i <= n; i++) {
    if (i & 1) {
        // 处理奇数位置
        int tot = -1;
        for (int j = 0; j < del2[a[i]].size(); j++) {
            if (ste.empty() || -e[del2[a[i]][j]] != *ste.begin()) {
                tot = j; break;
            }
            ste.erase(ste.begin());
        }
        // ... 复杂匹配逻辑
    } else {
        // 处理偶数位置
        // ... 对称逻辑
    }
}

使用贪心策略在多重集合中寻找最优匹配。

算法正确性

模式分析

• 模式 $(i,j)$：偶数位置用 $i$，奇数位置用 $j$
• 有效段数 $x$ 表示可以保留的连续段数量
• 操作次数 = 总元素数 - (保留的偶数位元素 + 保留的奇数位元素 - 重叠修正)

贪心选择

通过维护奇偶位置的频率多重集合，优先选择出现频率高的数值组合。

复杂度分析

• 频率统计：$O(n)$
• 模式统计：$O(n)$
• 贪心匹配：$O(n \log n)$
• 总复杂度：$O(n \log n)$

关键技巧

1. 奇偶分离：分别统计奇偶位置的数值频率
2. 模式识别：识别有效的数值组合模式
3. 贪心匹配：使用多重集合进行最优匹配
4. 重叠修正：处理连续相同模式的段数修正