https://codeforces.com/contest/985/problem/A
题目大意
给出 $1 \times n$ 的棋盘且 $n \ (\le 100)$ 为偶数。棋盘格为黑白相间的。给出 $n / 2$ 个棋子的位置，问最小的移动步数使得棋子都在同色格子中。棋子不能占据同样的格或相互跨越，给出最小的移动步数。
简要题解
因为无论移动到黑格还是白格，棋子不能相互跨越则最终棋子的顺序与移动前一致。显然最小步数是所有棋子初始位置与目标位置的差的和。我们需要构造性的证明这件事总是办得到的。
我们找到最右一个需要右移的元素 $i$，注意到这个元素右侧到其目标位置之间不会有元素，因为如果有，不妨设其为 $j$ 则 $org[i] < org[j] <= dis[i]$ 则此时一定有 $org[j] <= dis[i] < dis[j]$ 即 $j$ 也是一个需要右移的元素，矛盾。左侧同理。
于是我们总可以重复的去找，最右边需要右移的右移，最左边需要左移的左移，直到找不到了，说明所有元素已经归位。
（证明还是有点小烦，还不如让输出个方案）
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n / 2);
for (int i = 0; i < n / 2; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int sum = 0;
for (int i = 1, j = 0; i <= n; i += 2, j++) {
sum += abs(a[j] - i);
}
int ans = sum;
sum = 0;
for (int i = 2, j = 0; i <= n; i += 2, j++) {
sum += abs(a[j] - i);
}
cmin(ans, sum);
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Slay the Dragon - Educational Codeforces Round 114 (Rated for Div. 2)