题意

给定一张初始点数为 的卡牌，每次操作可以将某张卡牌点数 、，或复制一张相同的卡牌并放入序列中。求将这张卡牌变为指定的 张点数分别为 的卡牌序列，最少需要多少次操作。

题解

我们的目标是将 张牌变为 张牌，由于只有“复制”操作能使卡牌总数增加 ，因此要得到 张卡牌，必定且只需执行刚好 次复制操作。

接下来考虑如何最小化修改点数（即 和 ）的操作次数。我们将所有的卡牌点数（包括初始起点 和目标序列中的所有 ）映射到一维数轴上。设点集 的最小值为 ，最大值为 。 由贪心可知，在 处复制出额外的牌，让它们分别向左、向右单调移动。途中只要路过目标点就复制一张“留下来”，本体则继续向两端边界进发，由于不走回头路，最终的移动步数恰好就是区间跨度 。 综上所述，最少的总操作次数固定为 。

复杂度

  • 时间复杂度：
  • 空间复杂度：

参考代码与链接

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void solve() {
    int n;
    ll x;
    cin >> n >> x;
    
    ll mn = x, mx = x;
    for (int i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        mn = min(mn, a);
        mx = max(mx, a);
    }
    
    ll ans = (n - 1) + (mx - mn);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}