自动搬运

查看原文

来自洛谷，原作者为

	t14Zack 自闭少年常小菜

搬运于2025-08-24 21:59:32，当前版本为作者最后更新于2018-04-28 21:31:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

好吧，我承认这题我开始想简单了
我直接按照伪代码改过来的，结果只过了可怜的5个点……
错误代码：

#include <cstdio>
int a[100010];
int main() {
    int n, t, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    bool sorted = false;
    while(sorted == false) {
        sorted = true;
        ans++;
        for (int i = 0; i <= n-2; i++)
            if(a[i+1] < a[i])
                t = a[i+1], a[i+1] = a[i], a[i] = t, sorted = false;
    }
    printf("%d\n", ans);
    return 0;
}

这题我们应该自己把输出moo的次数算出来，而不能直接用它给的伪代码。
那我们就用样例1 5 3 8 2来说明自己如何找出moo的次数：
1 3 5 2 8
1 3 2 5 8
1 2 3 5 8
1 2 3 5 8
我们发现，2向左移的最多。
再举几个例子 1 9 5 8 3 2：
1 5 8 3 2 9
1 5 3 2 8 9
1 3 2 5 8 9
1 2 3 5 8 9
2向左移的最多。
再如：9 1 3 7 2：
1 3 7 2 9
1 3 2 7 9
1 2 3 7 9
1 2 3 7 9
1在向左移，但2向左移的最多。
从这几个例子中，我们可以发现： _ moo的次数就是往左移的最多的次数_ +1。
如：9 1 3 7 2中，1左移了1个，而2左移了了3个，结果就是3+1=4次。
为什么要+1呢？因为添加1来说明排序时进行代码中的最后一次迭代，也就是我每次最后写2次排好序的序列的原因。
我们可以再用样例来说明一下怎样算出向左移的最多的个数:
1 5 3 8 2
转换成：
0 1 2 3 4
接着排序，2个序列为：
1 2 3 5 8
0 4 2 1 3
设第2个数组为a，max{a-当前位置} 就是向上冒的最多的了，最后再+1就行了。
上代码：

#include <cstdio>
#include <algorithm>
struct node {
	int in;
	int zhi;
} a[100000];
bool cmp (const node &a, const node &b) {
	return a.zhi < b.zhi || (a.zhi == b.zhi && a.in < b.in);
}
int max(int a, int b) {return a < b ? b : a;}
int main() {
	int n, ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i].zhi), a[i].in = i;
	std::sort(a, a+n, cmp);
	for (int j = 0; j < n; j++)
		ans = max(ans, a[j].in-j);
	printf("%d\n", ans+1);
}