屠魔而又成魔
2022-02-27 16:47
采纳率: 85.7%
浏览 36

C++在刷题的时候遇到了一个类似与排序的题,没有思路,如何解决?

题目描述:

在一件似乎很熟悉的事情中,农夫约翰正在排队ñ奶牛(1≤N≤105),方便编号1 … N, 一张照片。
最初,奶牛按顺序排列一种1,一种2, … ,一种ñ从左到右。Farmer John 的目标是按顺序排列奶牛b1, … ,bñ从左到右。为此,他可以对排序进行一系列修改。每个修改都包括选择一头奶牛并将其向左移动一些位置。

请计算农民约翰按所需顺序排列奶牛所需的最少修改次数。

输入格式(输入来自终端/标准输入):
输入的第一行包含ñ. 第二行包含一种1,一种2, … ,一种ñ. 第三行包含b1,b2, … ,bñ.
输出格式(打印输出到终端/标准输出):
打印生产 Farmer John 所需订单所需的最少修改次数。
样品输入:
5
1 2 3 4 5
1 2 3 4 5
样品输出:
0
在此示例中,奶牛已按所需顺序排列,因此无需修改。

样品输入:
5
5 1 3 2 4
4 5 2 1 3
样品输出:
2
在这个例子中,两个修改就足够了。这是 Farmer John 重新排列奶牛的一种方法:

选择奶牛4并将其向左移动四个位置。
选择奶牛2并将其向左移动两个位置。
5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题