题解：P17722 [SCP-S 2026] 档案 / file

· · 题解

传送门。

思路

不难发现，对于一个档案，只有新加入的档案的编号小于它，它的下标才会变化，并且每个档案的下标都只增不减。

所以插入档案集合的代价等同于插入前核心档案的下标之和，再加上它们的总移动距离，即编号为 x 核心档案的移动距离就是新加入的档案集合中编号小于 x 的档案个数。

那我们贪心地想，新加入的档案集合让所有核心档案的移动距离肯定是越小越好。

为什么？\ 因为核心档案的下标位置也是只增不减，所以往后的插入操作都是基于当前核心档案的下标位置进行变化的。\ 这就跟排队接水一样，尽管最后核心档案的下标是确定的，但过程中它们的下标却会因为不同的插入顺序而改变，因而下标总和改变。

因此，我们在输入档案集合时，用二分查找编号比它大的核心档案的数量，即它会影响的核心档案的个数，然后记录到一个 cnt 数组里。

然后将 cnt 按升序排序，最后统计答案即可。

:::success[AC 代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+5;
ll n,m,ans,tmp;
ll a[N],cnt[N];
int main(){
    scanf("%lld%lld",&n,&m),tmp=(n*(n+1))>>1ll;
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(ll i=1,l,x;i<=m;i++){
        scanf("%lld",&l);
        for(ll j=1;j<=l;j++)scanf("%lld",&x),cnt[i]+=n-(upper_bound(a+1,a+1+n,x)-a-1);
    }sort(cnt+1,cnt+1+m);
    for(ll i=1;i<=m;i++)ans+=(tmp+=cnt[i]);
    printf("%lld",ans);
    return 0;
}

:::