题解：P11908 [NHSPC 2023] G. 博物館（@Arthur2024）

· · 题解

题目意思

题目传送门

题目让我们在 n 个作品中，把价值最昂贵的 k 个作品移至最前面的几个位置，并且要求每次只能将相邻的两个作品交换，问最少要交换几次。

思路

假如我们先将价值最昂贵的 k 个作品找出来，把它们一个个往前搬，但是这样不一定是最优的。

我们可以想到一个作品在往前搬时，有可能会把另一个也要往前搬的作品交换，此时另一个作品的位置会随着前面的哪个作品的交换往后退，这导致后面再搬这个作品时，会比原来多搬一次。

为了避免这种情况，我们会优先搬最靠前的要搬的作品，这样在搬的过程就不会影响后面的作品，并且第一个搬的作品最后会到第一个位置，第二个搬的作品最后会到第二个位置，以此类推。

注意不能找出最昂贵的 k 个作品中最便宜的作品进行比较，因为如果出现相同价格的作品时，找出的作品数量可能超过了 k 个。

我这里用一个数表示两个数，即将第一个数乘一个比第二个数可能的范围还要大的数再加上第二个数，这样做是为了后面排序做准备，这样就能做到第一个数小的在前，大的在后，相同的第二个数小的在前，大的在后，记得开 longlong。

我这里把 c_i 作为第一个数，n-i 作为第二个数，而不是 i，因为排序时我们希望把在相同价值的所有作品中，原本位置更靠前的作品在 a 数组中更靠后，再从 a 数组中提取最后的 k 个元素，即优先提取价值最高的，价值相等的作品中，先提取原本位置最靠前的。

提取的时候注意要先取模，再用 n 减取模后的数，因为之前存储时也是用 n 去减 i，后面 -k+n-i 是因为每个要搬的作品最后的位置不同，第一个要搬的作品最后在第一个的位置，第 k 个要搬的作品最后在第 k 个的位置。

最后记得开 longlong。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[100010];
signed main(){
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    for(int i=1;i<=n;i++){
        c[i]=c[i]*1000000+n-i;//用c数组存储的一个数存储两个数，方便排序
    }
    sort(c+1,c+n+1);//排序
    for(int i=n;i>n-k;i--){
        ans+=n-c[i]%1000000-k+n-i;//提取每个作品需搬的次数
    }
    cout<<ans;
    return 0;
}

谢谢观看！