「CCO 2020」赶作业 ddl 题解

算法思路分析

这是一个排列重排问题，需要通过相邻交换将初始排列 $(1,2,\dots,N)$ 重排，使得每个位置 $i$ 上的数不超过 $d_i$，并求最小交换次数。

关键观察

1. 相邻交换与逆序对：相邻交换次数等于排列的逆序对数
2. 可行性条件：必须存在一个排列，使得对于所有 $i$，有 $a_i \le d_i$
3. 贪心策略：从大到小分配数字，每次选择最靠右的可用位置

核心算法：贪心 + 树状数组

算法步骤

1. 可行性检查

sort(a + 1, a + 1 + n);
bool flag = true;
for(int i = 1; i <= n; i++)
    if(i > a[i]) {  // 检查排序后的d_i是否满足条件
        flag = false;
        break;
    }

原理：将 $d_i$ 排序后，必须满足 $d_i \ge i$（类似Dilworth定理）

2. 贪心分配

priority_queue<int> q;
for(int i = n; i >= 1; i--) {
    for(int x : v[i]) q.push(x);  // 将所有d_j = i的位置加入堆
    int cur = q.top();  // 选择最靠右的位置
    ans += bit.query(cur);  // 计算逆序对
    bit.update(cur, 1);  // 标记该位置已使用
    q.pop();
}

贪心策略：

• 从最大的数字 $n$ 开始分配
• 对于数字 $i$，选择满足 $d_j \ge i$ 的最靠右位置 $j$
• 这样最小化当前数字产生的逆序对

3. 逆序对统计

使用树状数组统计逆序对：

struct BIT {
    int tree[N];
    void update(int k, int x) {
        while(k <= n) {
            tree[k] += x;
            k += lowbit(k);
        }
    }
    int query(int k) {
        int res = 0;
        while(k > 0) {
            res += tree[k];
            k -= lowbit(k);
        }
        return res;
    }
} bit;

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 排序：$O(n \log n)$
  • 优先队列操作：$O(n \log n)$
  • 树状数组操作：$O(n \log n)$
• 空间复杂度：$O(n)$

算法正确性证明

可行性条件

只有当排序后的 $d_i$ 满足 $d_i \ge i$ 时，才存在满足条件的排列。这保证了对于前 $k$ 小的约束，至少有 $k$ 个位置可以容纳前 $k$ 小的数字。

最优性证明

从大到小分配并选择最靠右的可用位置，可以保证：

1. 较大的数字尽量靠右，减少与后面数字的逆序对
2. 为较小的数字留出更多靠左的位置
3. 总体逆序对数最小化

算法标签

主要分类

• 贪心算法 ⭐⭐⭐⭐⭐
• 树状数组 ⭐⭐⭐⭐
• 逆序对计数 ⭐⭐⭐⭐

技术子标签

• 优先队列 ⭐⭐⭐⭐
• 排序 ⭐⭐⭐
• 组合优化 ⭐⭐⭐⭐

问题类型

• 排列重排 ⭐⭐⭐⭐
• 约束满足 ⭐⭐⭐⭐
• 最小化交换 ⭐⭐⭐⭐

样例验证

样例1

输入: 4
       4 4 3 2
输出: 3

算法过程：

1. 可行性检查：排序后为 [2,3,4,4]，满足条件
2. 贪心分配：数字4→位置2，数字3→位置3，数字2→位置4，数字1→位置1
3. 计算逆序对：得到3

样例2

输入: 3  
       1 1 3
输出: -1

排序后为 [1,1,3]，但 $1 < 1$（第一个位置），无解。

算法优势

1. 高效性：$O(n \log n)$ 处理 $n \leq 2 \times 10^5$ 的数据
2. 正确性：严格的可行性检查和最优性保证
3. 简洁性：结合贪心思想和数据结构，代码清晰易懂

该解法通过巧妙的贪心策略和逆序对统计，成功解决了带约束的排列重排问题，展现了组合优化与数据结构的完美结合。