Farmer John 正在将他的 N 头奶⽜ ( 1≤N≤105 ) 排成⼀排，⽅便地编号为 1…N ，以便拍照。 最初，奶⽜从左到右按照 a1,a2,...,aN 的顺序排列 。Farmer John 的⽬标是按照 b1,...,bN 从左 到右的顺序排列奶⽜。为此，他可以对排序进⾏⼀系列修改。每个修改都包括选择⼀头奶⽜ 并将其向左移动⼀些位置。 请计算农⺠约翰按所需顺序排列奶⽜所需的最少修改次数

题目翻译

农夫 John 正在将他的 $N$ 头奶牛 $(1\leq N\leq 10^5)$ 排成一排，方便地编号为 $1…N$，以便拍照。最初，奶牛从左到右按照 $a_1,a_2,...,a_N$ 的顺序排列。农夫 John 的目标是按照 $b_1,...,b_N$ 从左到右的顺序排列奶牛。为此，他可以对排序进行一系列修改。每个修改都包括选择一头奶牛并将其向左移动一些位置。请计算农夫 John 按所需顺序排列奶牛所需的最少修改次数。

题解

这道题其实是一道经典的贪心问题——交换相邻逆序对。

首先，我们可以发现，对于第 $i$ 头奶牛，它需要向左移动的距离 $d_i$ 为 $b_i$ 在 $a$ 数组中的下标减去 $i$。也就是说，对于每头奶牛，我们都可以知道它需要向左移动的距离。

但是，我们并不需要真的进行移动，只需要记录每头奶牛需要向左移动的距离 $d_i$，并计算出它们的交换次数即可。

因为我们只能交换相邻两个位置上的奶牛，所以我们可以从左到右遍历 $b$ 数组，对于每个 $b_i$，我们找到它在 $a$ 数组中的位置 $j$，并把 $a_j$ 与 $a_{j-1}$ 交换，直到 $a_j$ 到达 $i$ 的位置。

为什么这个方法是正确的呢？因为我们每次都是交换相邻逆序对，所以每次交换后，我们就让一个相邻逆序对消失了。因此，我们最多只需要进行 $N$ 次交换。

代码

相关问题

3. 放牧(herding) 【问题描述】 farmer john的n头奶牛,总是会迷路走到农场上遥远

farmer john的n头奶牛总是会迷路走到农场上遥远的地方。这让农民感到很困扰，因为要找回这些迷路的奶牛并不容易，而且迷路的奶牛也可能会受到一些危险。

为了解决这个问题，农民决定开始进行放牧。他们雇佣了一些牧羊犬来帮助管理奶牛，并且修建了一些围栏和栅栏来限制奶牛的活动范围。农民还在每头奶牛的脖子上悬挂了一块小小的发光标签，这样就可以在夜晚更容易地找到它们。

农民还在农场周围设置了一些监控摄像头，以便在奶牛走丢时能够及时发现并寻找它们的方向。此外，农民还雇佣了一些专业的放牧人员来负责管理奶牛的日常放牧工作，确保它们不会迷路。

通过这些措施，农民成功地解决了奶牛经常迷路的问题。现在，奶牛们能够在农场上自由地放牧，而农民也更加放心，因为他们知道奶牛们不会再迷路了。这不仅减少了农民的工作量，也提高了奶牛的安全性和健康状况。

Farmer John 正在分配他的 N (1 <= N <= 25,000) 头奶牛在谷仓周围做一些清洁杂务。 他将一天分为 T 个时间段（1 <= T <= 1,000,000）编号为1...T。每头奶牛只能在一天中的某个连续的时间段进行清洁工作。 任何被选中执行清洁任务的奶牛都将在整个工作时间段内工作。您的任务是帮助 Farmer John 分配一些奶牛轮班，以便每个时间段至少分配一头奶牛，并且参与清洁的奶牛尽可能少。 如果无法为每个班次分配一头奶牛，则输出 -1。

这是一个算法问题，我可以回答。这个问题可以使用贪心算法来解决。首先，将所有奶牛的可用时间段按照结束时间从早到晚排序。然后，从第一个时间段开始，选择能够在这个时间段内工作的奶牛中结束时间最早的那头奶牛进行分配。接着，从下一个时间段开始，选择能够在这个时间段内工作的奶牛中结束时间最早的那头奶牛进行分配，以此类推。如果在某个时间段无法找到可用的奶牛，则输出 -1。