Out of Sorts II 题解

题面:

翻译:

贝西又写了一段代码进行冒泡排序.
对于给出的一组数据,在排序完成之后,moo语句会被执行多少次?

输入:

第一行是一个整数n,代表输入的数字有多少个
后面n行是待排序的数字

输出:

输出一个整数,代表moo执行的次数.

题目分析:

我们先把他给出的数据排序好,然后用一个数组c[]记录他每个数据最终会移动到哪个位置.
注意要让移动的幅度尽量少.
比如:
排序前是1515
排序后是 1155
这个第三个位置上的’1’,是应该移到第二位而不是第一位.

然后从头开始处理c数组

每一次进行循环,都可以把一个应该在后面的数字移到后面.
所以我们从i=1开始判断到i=n,原本在i位置前面并且要移动到i位置后面的数字的个数为ans.
找到这个ans的最大值.

这个最大值就是答案.

代码:

#include<stdio.h>
#include<algorithm>
#include<memory.h>

long n, a[100100], s[100100], c[100100], ans, maxans = 1;
bool match[100100];

long findm(long m){
    long i = m;
    while(s[i] == s[m]) i++;
    i--;
    while(s[i] == s[m] && !match[i]) i--;
    i++;
    while(!match[i]){
        match[i] = 1;
        return i;
        i++;
    }
}

long find(long l, long r, long i){
    long m = (l + r) >> 1;
    if(s[m] == i)   return findm(m);
    if(i < s[m])    return find(l, m-1, i);
    else return find(m+1, r, i);
}

int main(){
    scanf("%ld", &n);
    for(long i = 1; i <= n; ++i){
        scanf("%ld", a+i);
        s[i] = a[i];
    }
    std::sort(s+1, s+n+1);
    for(long i = 1; i <= n; ++i){
        c[i] =find(1,n,a[i]);
    }

    memset(match, 0, sizeof(match));

    for(long i = 1; i <= n; ++i){
        if(c[i] > i)
            ans++;
        if(match[i])
            ans--;
        match[c[i]] = 1;
        maxans = (maxans>ans)?maxans:ans;
    }
        printf("%ld\n", maxans);
}