P10155

HasNoName · 2024-02-13 18:42:09 · 题解

题目

给出一个 n 的排列，每次可以将一个数移到它后面第一个比它大的数前面，问最少要多少次才能将数列排好序。

思路

无解：

• 如果数字 n 不在最后面则无解，因为 n 无法移到最后面，则序列不可能有解。
• 如果数列有解，则 n 一定在最后面，因为 n 在最后面，可以把 n-1 移到 n 前面，又可以把 n-2 移到 n-1 前面，以此类推。

如果有解，从后往前匹配每一位，如果不同，次数加一，把那个数字移到前面，一定最优。

代码（60分）

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int a[N],n,w[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        w[a[i]]=i;
    }
    if(w[n]!=n)//无解
    {
        cout<<-1<<'\n';
        return 0;
    }
    int k=0;
    for(int i=n;i>=1;i--)
    {
        if(w[i]==i)continue;
        k++;
        for(int j=w[i];j<i;j++)//前移
        {
            a[j]=a[j+1];
            w[a[j]]=j;
        }//以计算过的数字不用再计算了
    }
    cout<<k<<'\n';
    return 0;
}

由于上面代码时间复杂度为 O(n^2) 所以 Subtask 4 会超时。

由于答案只跟匹配数有关，所以只用看匹配数。因为如果一个数在应该在的位置后面，后面一定会到指定位置，只统计在指定位置前面的数字即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int a[N],n,w[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i<a[i])sum++;//i表示当前位置，a[i]表示目标位置
    }
    if(a[n]!=n)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<sum<<'\n';
    return 0;
}

但发现 WA 了很多点，是因为有些在指定位置后面的数因为有数移到前面了，所以答案少了。

可以用树状数组统计在这个数前面的比它大的数的个数，计算目前位置。

代码（100分）

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int a[N],n,w[N],c[N];
int lowbit(int x)
{
    return x&(-x);
}
void add(int k,int x)//在k位置增加x
{
    if(k>n)return;
    c[k]+=x;
    add(k+lowbit(k),x);
}
int sum(int k)//当前比k小的数的个数
{
    if(k==0)return 0;
    return c[k]+sum(k-lowbit(k));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        add(a[i],1);
        if(i-sum(n)+sum(a[i])<a[i])ans++;//i表示移动后的位置
    }
    if(a[n]!=n)
    {
        cout<<-1<<'\n';
        return 0;
    }
    cout<<ans<<'\n';
    return 0;
}

复杂度：O(nlogn)。

AC 记录。