首页 > 试题广场 >

两个序列

[编程题]两个序列

热度指数：1426 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小强有两个序列 $\mathit a$ 和 $\mathit b$ ，这两个序列都是由相同的无重复数字集合组成的，现在小强想把 $\mathit a$ 序列变成 $\mathit b$ 序列，他只能进行以下的操作：
从序列 $\mathit a$ 中选择第一个或者最后一个数字并把它插入 $\mathit a$ 中的任意位置。
问小强至少需要几次操作可以将序列 $\mathit a$ 变为序列 $\mathit b$ 。

输入描述:

一行一个整数表示序列的长度。
接下来两行每行个整数。
第一行表示序列，第二行表示序列。



保证给出的序列符合题意。

输出描述:

输出一行一个整数表示答案。

示例1

输入

4
4 2 3 1
1 2 3 4

输出

算法知识视频讲解

寒冰-侠客

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[100005],b;
map<int,int>mp;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,ans=0,cnt=0;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
        cin>>b,mp[b]=i;
    for(i=1;i<=n;i++)
        a[i]=mp[a[i]];
    for(i=1;i<=n;i++)
    { /**< 求最长连续上升子段，其他部分都得移动插入 */
        if(a[i]>a[i-1])
            ans=max(ans,++cnt);
        else
            cnt=1;
    }
    cout<<n-ans;
    return 0;
}

发表于 2021-05-02 18:53:13 回复(3)

RobertSJTU

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> a(n, 0);
    vector<int> b(n, 0);
    unordered_map<int, int> mp;
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<n; i++) cin>>b[i];
    for(int i=0; i<n; i++) mp[b[i]]=i;
    int cur=0;
    int ans=0;
    int lb=0;
    for(int i=0; i<n; i++) {
        if(mp[a[i]]>=lb) cur++;
        else {
            ans=max(ans, cur);
            cur=1;
        }
        lb=mp[a[i]];
    }
    cout<<n-ans;
    return 0;
}

转化成最大连续上升子序列问题，子序列里面的元素可以不移动，子序列之外的元素需要移动插入到子序列中去，所以答案就是序列总长度减去最大连续上升子序列长度。

发表于 2021-05-31 14:37:45 回复(4)

狂奔的芒果派

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**

 * @date 2021/8/27 - 16:04
 */
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = cin.nextInt();
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(cin.nextInt(),i);
        }
        // 将序列表示成b的下标
        for (int i = 0; i < n; i++) {
            a[i] = map.get(a[i]);
        }
        // 求下标最长连续上升序列
        int max = 1;
        int cur = 1;
        // 从第二个开始计算
        for (int i = 1; i < a.length; i++) {
            if(a[i]>a[i-1]) {
                cur++;
                max = Math.max(max,cur);
            }else {
                cur = 1;
            }
        }
        System.out.println(n-max);
    }
}

发表于 2021-08-27 16:21:07 回复(0)

Java

牛客837169005号

补个 Java 版本的

import java.util.*;
public class Main {
    /*
    更改题目   a=[D,B,C,A]; b=[A,B,C,D]
    对 b 做映射  A->0; B->1; C->2; D->3
    那么对应的 a 可根据映射规则更改为 a'=[3,1,2,0]
    之后对 a' 做最长连续上升子数组即可
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i ++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i ++) {
            b[i] = sc.nextInt();
        }
        // 对 A 里面的数进行重新映射
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i ++) {
            map.put(b[i], i);
        }
        // 利用映射规则对 B 进行更新映射
        for (int i = 0; i < n; i ++) {
            a[i] = map.get(a[i]);
        }
        // 对更改之后的 b 做最长连续上升子序列
        int res = 0;
        int cur = 1;
        for (int i = 1; i < n; i ++) {
            if (a[i]>a[i-1]) {
                cur += 1;
                res = Math.max(res, cur);
            } else {
                cur = 1;
            }
        }
        System.out.println(n - res);
    }
}

发表于 2021-08-01 11:39:38 回复(0)

有一个地方.

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r = {}
for i in range(1, n + 1) :
    r[b[i - 1]] = i
for i in range(n) :
    a[i] = r[a[i]]
cnt, ans = 1, 1
for i in range(1, n) :
    if a[i] > a[i - 1] :
        cnt += 1
        ans = max(ans, cnt)
    else :
        cnt = 1
print(n - ans)

发表于 2021-04-29 21:07:20 回复(3)

梦已醒了

思路就是找出a数组中满足条件的最大连续子数组的长度，条件为子数组中的元素出现在b数组中的先后顺序保持不变。

import sys

read = sys.stdin.readline
n = int(read())
a_arr = list(map(int, read().split()))
b_arr = list(map(int, read().split()))
# a_map = {}
b_map = {}
for i in range(n):
    # a_map[a_arr[i]] = i
    b_map[b_arr[i]] = i

ans = 1
cnt = 1
for i in range(1, n):
    # if a_map[b_arr[i - 1]] < a_map[b_arr[i]]:
    if b_map[a_arr[i - 1]] < b_map[a_arr[i]]:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 1
print(n - ans)

发表于 2024-08-16 23:23:07 回复(0)