CF｜Building Permutation

Codeforces题解｜285C - Building Permutation

---

题目信息 📚

【题目描述】

Permutation $p$ is an ordered set of integers $p_1, p_2, \ldots, p_n$, consisting of $n$ distinct positive integers, each of them does not exceed $n$. We’ll denote the $i$-th element of permutation $p$ as $p_i$. We’ll call number $n$ the size or the length of permutation $p_1, p_2, \ldots, p_n$.

You have a sequence of integers $a_1, a_2, \ldots, a_n$. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves needed to build a permutation from this sequence.

【输入】

The first line contains the integer $n$ $(1 \leq n \leq 3 \cdot 10^5)$ — the size of the sought permutation. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(-10^9 \leq a_i \leq 10^9)$.

【输出】

Print a single number — the minimum number of moves.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

【输入样例1】

2
3 0

【输出样例1】

2

【输入样例2】

3
-1 -1 2

【输出样例2】

6

【题目来源】

https://codeforces.com/problemset/problem/285/C

---

题目解析 🍉

【题目分析】

很容易猜到の贪心策略：令排序后的 a[i] → i

具体数学证明其实有点困难，多做题提高直觉吧～

来自GPT的证明：

To prove that this approach is optimal, let’s consider two elements $a_i$ and $a_j$ such that $a_i < a_j$ and their corresponding targets in the permutation are $t_i$ and $t_j$ respectively. For the total cost to be minimized, it must be the case that $t_i \leq t_j$.

If $t_i > t_j$, you can swap $t_i$ and $t_j$, which will decrease the total cost because the sum of $|a_i - t_j| + |a_j - t_i|$ is less than $|a_i - t_i| + |a_j - t_j|$. This swap contradicts the assumption that we have an optimal solution.

Thus, for every pair $(a_i, a_j)$ with $a_i < a_j$, their targets must be in non-decreasing order. This ordering is exactly what is achieved by sorting the sequence $a$.

【C++代码】✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n, a[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据并且排序
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);

    // 贪心策略：令排序后的a[i] -> i
    LL cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += abs(a[i] - i);
    }
    cout << cnt << endl;

    return 0;
}