2025-8-7

猿柒

23天前发布

2025-8-7
- codeforces-1130B
  - 题意描述
  - 解题思路
  - 解题代码

2025-8-7

codeforces-1130B

题意描述

给定一个长度$2n$的序列($1\le a_i \le n$), 两人都从最左边出发，

每次移动1，且只可以从小到大取，每个$a_i$只可以取一次，

求都取到一个$1 \sim n$的的排列的最小步数。

解题思路

贪心
起点为0
每次两人同时走到$a_i = i(1 \le i \le n)$的两个位置，有两个方案，走到贡献较小的方案即可。

解题代码

void solve()
{   
    int n;
    cin >> n;

    vector<vector<int>> p(2*n);
    for(int i = 0; i < 2*n; i++){
        int a;
        cin >> a;
        p[a].push_back(i);
    }
    ll ans = 0;
    int cur = 0, ocur = 0;
    
    for(int i = 1; i <= n; i++){
        int ne = (abs(p[i][0] - cur) + abs(p[i][1] - ocur) < abs(p[i][1] - cur) + abs(p[i][0] - ocur)) ? p[i][0] : p[i][1];
        int one = (abs(p[i][0] - cur) + abs(p[i][1] - ocur) < abs(p[i][1] - cur) + abs(p[i][0] - ocur)) ? p[i][1] : p[i][0];
        ans += abs(ne-cur) + abs(one-ocur);
        cur = ne;
        ocur = one;
    }

    cout << ans << nl;
}