恒__heng 2022-02-27 16:47 采纳率: 90%
浏览 76
已结题

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条回答 默认 最新

  • 真相重于对错 2022-02-27 19:55
    关注

    我是这样想的
    5 1 3 2 4
    ---》
    4 5 2 1 3;
    按结果数据的位置把输入重写
    2 4 5 3 1
    因为 4排在第一个, 5排在第二个,2 排在第三个,1 排在第四个 3排在第5个
    找出从右往左找出有多少个逆序的就可以,这是是3和1 结果是2

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 3月8日
  • 已采纳回答 2月28日
  • 创建了问题 2月27日

悬赏问题

  • ¥100 嵌入式系统基于PIC16F882和热敏电阻的数字温度计
  • ¥20 BAPI_PR_CHANGE how to add account assignment information for service line
  • ¥500 火焰左右视图、视差(基于双目相机)
  • ¥100 set_link_state
  • ¥15 虚幻5 UE美术毛发渲染
  • ¥15 CVRP 图论 物流运输优化
  • ¥15 Tableau online 嵌入ppt失败
  • ¥100 支付宝网页转账系统不识别账号
  • ¥15 基于单片机的靶位控制系统
  • ¥15 真我手机蓝牙传输进度消息被关闭了,怎么打开?(关键词-消息通知)