P3656 [USACO17FEB]Why Did the Cow Cross the Road I P

    • 51通过
    • 253提交
  • 题目提供者FarmerJohn2
  • 标签 USACO 2017
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    Why did the cow cross the road? We may never know the full reason, but it is certain that Farmer John's cows do end up crossing the road quite frequently. In fact, they end up crossing the road so often that they often bump into each-other when their paths cross, a situation Farmer John would like to remedy.

    Farmer John raises $N$ breeds of cows ($1 \leq N \leq 100,000$), and each of his fields is dedicated to grazing for one specific breed; for example, a field dedicated to breed 12 can only be used for cows of breed 12 and not of any other breed. A long road runs through his farm. There is a sequence of $N$ fields on one side of the road (one for each breed), and a sequence of $N$ fields on the other side of the road (also one for each breed). When a cow crosses the road, she therefore crosses between the two fields designated for her specific breed.

    Had Farmer John planned more carefully, he would have ordered the fields by breed the same way on both sides of the road, so the two fields for each breed would be directly across the road from each-other. This would have allowed cows to cross the road without any cows from different breeds bumping into one-another. Alas, the orderings on both sides of the road might be different, so Farmer John observes that there might be pairs of breeds that cross. A pair of different breeds $(a,b)$ is "crossing" if any path across the road for breed $a$ must intersect any path across the road for breed $b$.

    Farmer John would like to minimize the number of crossing pairs of breeds. For logistical reasons, he figures he can move cows around on one side of the road so the fields on that side undergo a "cyclic shift". That is, for some $0 \leq k < N$, every cow re-locates to the field $k$ fields ahead of it, with the cows in the last $k$ fields moving so they now populate the first $k$ fields. For example, if the fields on one side of the road start out ordered by breed as 3, 7, 1, 2, 5, 4, 6 and undergo a cyclic shift by $k=2$, the new order will be 4, 6, 3, 7, 1, 2, 5. Please determine the minimum possible number of crossing pairs of breeds that can exist after an appropriate cyclic shift of the fields on one side of the road.

    为什么牛要过马路?我们可能永远都不知道全部原因,但肯定的是,农民约翰的牛经常穿过马路。事实上,他们经常过马路,当他们的路径交叉时,他们经常碰到对方,这是约翰希望改进的情况。

    农夫约翰将奶牛分成了$N$个不同的品种($1\le N\le 100000$),他的每一个田地都是专门为一种特定的品种放牧; 例如,专门用于品种$12$奶牛的田地只能用于品种$12$的奶牛,而不能用于任何其他品种的奶牛。一条长长的路穿过他的农场。道路一侧有$N$个田地(每个品种一个),道路另一侧也有$N$个田地(每个品种也有一个)。所以,当一头牛穿过马路,它会穿过特定品种的两个田地。

    如果农民约翰更仔细的研究他的计划,他会在道路两旁订购同品种田地,所以每个品种的两个田野将直接穿过彼此的道路。这样就可以让奶牛随意过马路,而不会有不同品种的牛碰撞在一起。唉,但现在道路两边的田地可能不一样,所以农民约翰明白,可能会有一对品种$(a,b)$是交叉的当且仅当是一对不同的品种,且道路上一边田地品种a上的任何路线都与道路另一边田地品种b的任何路线相交 。

    农民约翰希望尽量减少品种的交叉对数。由于物流方面的原因,他表示,他可以在道路的一边移动牛,所以那边的田地可以“循环转移”。也就是说,对于一些品种$k(0\le k\le N)$牛来说,品种k的每头牛都会重新移动到新的领域,最后一个田地的奶牛将会移动到第一个田地,所以他们现在已经填补了第一个田地。一个例子,如果道路一侧的田地开始按种类排列为3,7,1,2,5,4,6,并进行循环移位,新排列将为4,6,3,7 ,1,2,5.请编程确定在道路一侧的田野适当循环移动后存在的品种交叉对的最小值。

    输入输出格式

    输入格式:

    The first line of input contains $N$. The next $N$ lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range $1 \ldots N$. The last $N$ lines describe the order, by breed ID, of the fields on the other side of the road.

    一行包含$N$ ($1 \leq N \leq 100,000$)与$K$ ($0 \leq K < N$),接下来$N$行按顺序描述了小路一旁田地的品种的ID号,每一个ID号是一个在$1...N$之间的整数。倒数$N$行描述了小路另一旁田地的品种的ID号。

    输出格式:

    Please output the minimum number of crossing pairs of breeds after a cyclic shift of the fields on one side of the road (either side can be shifted).

    输出 循环移动道路侧的田野后,请输出可能的品种交叉对的最小数量(两边均可移动)

    输入输出样例

    输入样例#1: 复制
    5
    5
    4
    1
    3
    2
    1
    3
    2
    5
    4
    输出样例#1: 复制
    0

    说明

    感谢@Adscn提供翻译

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。