题解：P2995 [USACO10NOV] Cow Photographs G

Istruggle · 2025-05-28 09:39:50 · 题解

如果要求第一头奶牛必须站在第一个位置，那么答案就是逆序对个数，然后我们发现，所有可能的答案序列就是顺序序列的循环，因此如果我们能快速求出每循环一次的答案就能将问题解决。

我们考虑每次将最后一个数移到最前面，如果是第一次移动，那么这个数一定是最大的，所以如果这个数在原始序列中的位置为 p，那么则在新产生了 p-1 个逆序对的同时减少了 n-p 个逆序对。那么当我们再将倒数第二大的数移动到前面的时候该如何计算呢？可以发现，这一操作就相当于将最小的数变为最大的数，例如原序列为 1,2,3,4,5，变换后的序列为 6,2,3,4,5，由于相对大小没变，所以第二个序列就相当于将第一个序列中的 5 移到前面，这样就简单了，我们每次将最小的数变为最大的数，其实就是按从小到大的顺序考虑将每个数变为最大，然后按照前面的方法计算新的答案即可。