题解 P4378 【[USACO18OPEN]Out of Sorts S】

· · 题解

好吧，我承认这题我开始想简单了
我直接按照伪代码改过来的，结果只过了可怜的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);
}