自动搬运

查看原文

来自洛谷，原作者为

	HRLYB 正式AFO

搬运于2025-08-24 22:08:10，当前版本为作者最后更新于2019-08-14 20:12:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5200 Sleepy Cow Sorting

我们发现，如果数列的后缀是递增的，那么是可以不用处理的.

由此引申出一种思路：把整个序列分成两个部分，前一个部分是还未排好序的，后一个部分是已经排好序的.

又因为每头牛最多被移动一次（显然每次只能移动队头，最多$n-1$次就可以保证有序了），后缀不用移动，因此，从后往前数第一个不递减的数，1~它全都得移动（不然移动不了它），它的位置就是最小移动数.

最小移动数求得后，还要求每头牛移动的距离. 这也不难想到，该距离就是当前未排好序的序列的长度-1 加上 这个元素应该在排好序的序列中的位置前面元素的数量.

为此应该维护一个最长的上升后缀，每一次插入到这个数在上升后缀应该在的位置.

我们不妨设计$1-n$的数组，其中$1$表示该元素已经在排好序的序列中，$0$表示该元素还未排序. 那么我们就可以知道指定元素的“前面元素”的数量了.

也就是说，对于已排好的序列，我们需要一种数据结构，支持计算前缀和和单点修改.

而且1e5的数据规模，复杂度大约在$O(nlogn)$左右

不难想到使用树状数组.

然后本题就完成了.

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n,a[maxn],tree[maxn],ans[maxn];
int lowbit(int x){return x&(-x);}
void add(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;
}
int query(int x){
	int ret=0;
	for(int i=x;i;i-=lowbit(i))ret+=tree[i];
	return ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int k=0,sum=n;
	while(a[n-k]>a[n-k-1]){
		add(a[n-k],1);//加入有序序列
		sum--;
		k++;
	}
	add(a[n-k],1),sum--;//无论如何，都要把后缀的第一个元素加入，a[n-k]<a[n-k-1]，a[n-k]才是不降后缀的第一个元素
	for(int i=1;i<=sum;i++){
		add(a[i],1);
		ans[i]=sum-i+query(a[i]-1);//求有序序列前缀和
	}
	printf("%d\n",sum);
	for(int i=1;i<=sum;i++){
		printf("%d ",ans[i]);
	}
	return 0;
}

我们主要要学习这题的分段维护思想，分段处理是否排好序的情况，把复杂问题分解为已解决不影响后面操作和未解决两部分，既方便思考，也方便写代码.