教人做家务的网站,wordpress底部功能按钮,公司网页设计的设计过程,wordpress 比特币【题目来源】http://oj.ecustacm.cn/problem.php?id1812http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给定一个长度为 n 的排列 a#xff0c;需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出最小需要移动的元素个数。【输入格式】 第一行…【题目来源】http://oj.ecustacm.cn/problem.php?id1812http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给定一个长度为 n 的排列 a需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出最小需要移动的元素个数。【输入格式】 第一行为正整数 n1≤n≤100000。 第二行为 n 个整数表示排列 a。 第三行为 n 个整数表示排列 b。【输出格式】 输出一个数字表示答案即最小需要移动的元素个数。【输入样例】 5 5 1 3 2 4 4 5 2 1 3【输出样例】 2【算法分析】 ** 将原序列 a 重排为序列 b则原序列 a 中各元素在序列 b 中的位置 p[] 可通过以下代码获得tp[b[i]]i, p[i]tp[a[i]]** 分析位置序列 p[] 中每个数如果当前的数比左边的数小就不断左移否则不用移动。这是贪心算法的思路。 例如针对样例中给出的原始序列 a[][5 1 3 2 4] 中的各元素利用“tp[b[i]]i, p[i]tp[a[i]]”可得出它们在重排序列 b[][4 5 2 1 3] 中的位置序列为 p[][2 4 5 3 1]。显然通过观察位序的相对位置可知需要移动两个数字。【算法代码】
#include bits/stdc.h
using namespace std;const int N1e55;
int a[N],b[N];
int p[N]; //p[x]:subscript of number x in the b array
int tp[N];int main() {int n;cinn;for(int i1; in; i) cina[i];for(int i1; in; i) {cinb[i];tp[b[i]]i;}for(int i1; in; i) p[i]tp[a[i]];int ans0;int t0;for(int i1; in; i) {if(tp[i]) ans;tmax(t,p[i]);}coutansendl;return 0;
}/*
in:
5
5 1 3 2 4
4 5 2 1 3out:
2
*/
【参考文献】https://blog.csdn.net/weixin_43914593/article/details/131741061