题解 P8184 [USACO22FEB] Photoshoot 2 B

· · 题解

乍一看这道题可能没什么头绪，不如先看看 a_i 数组在最终获得的 b_i 数组里都处于什么位置，设为 c_i 。

以题中给出的样例 2 为例：

a_i = [5,1,3,2,4] b_i = [4,5,2,1,3]

映射数组 c_i = [2,4,5,3,1]

容易发现最后的结果是对 c_i 进行排序，当 c_i 为升序序列即 [1,2,3,4,5] 时，对应的 a_i 转为 b_i 。

即本题可转为类似 逆序对 的解法。

code：

c语言版本：

#include <stdio.h>
int n,a[100010],b[100010],c[100010];
int ans,maxn,i;
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        c[b[i]]=i;//建立映射数组
    }
    for(i=1;i<=n;i++) a[i]=c[a[i]];//用a[i]在映射数组中的位置，替换掉a数组
    for(i=1;i<=n;i++)
    {
        //a[i]>maxn?maxn=a[i]:ans++; 三目运算写法
        if(a[i]>maxn) maxn=a[i];
        else ans++;
    }
    printf("%d",ans);
    return 0;
}

c++版本：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],c[N];
int ans,maxn;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        c[b[i]]=i;
    }
    for(int i=1;i<=n;i++) a[i]=c[a[i]];
    for(int i=1;i<=n;i++) a[i]>maxn?maxn=a[i]:ans++; 
    cout<<ans;
    return 0;
}