中石油- 2018年第三阶段个人训练赛第三场-补题

E:http://exam.upc.edu.cn/problem.php?id=6347

题意：给你一个数组，利用冒泡排序，计算需要冒泡多少次，每次冒泡之前输出一串话，问这句话输出了多少次，因为是在之前输出，所以即使是本身排好序的也要输出一次，但是这里的冒泡是改进之后的冒泡，每次将最大的冒泡到最后之后还反向冒泡一次，将最小的冒泡到最前面。

思路：这里有一个规律就是，先将原数组排序，如果排序之后的位置在现在位置的后面，那么我们就需要将这个数字移动到后面去，就要加加，遇到之前已经移动过的就要减减，去峰值。有一个离散化的过程

代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int maxn = 100005;
 
int n;
int a[maxn];
struct node
{
    int x;
    int id;
}aa[maxn];
int b[maxn];
int vis[maxn];
int ans;
int tmp;
 
void init()
{
    ans = 1;
    tmp = 0;
    memset(vis , 0 , sizeof(vis));
}
 
void input()
{
    for(int i=0; i<n; i++)
    {
        scanf("%d" , &aa[i].x);
        aa[i].id = i;
    }
}
 
bool cmp(node x , node y)
{
    return x.x < y.x;
}
 
int main()
{
    while( scanf("%d" , &n) != EOF)
    {
        init();
        input();
        sort(aa , aa+n , cmp);
        for(int i=0; i<n; i++)
        {
            a[aa[i].id] = i;
            b[aa[i].id] = i;
        }
        sort(b , b+n);
        for(int i=0; i<n; i++)
        {
            if(vis[b[i]] == 1)
            {
                tmp--;
            }
            if(b[i] < a[i])
            {
                tmp++;
                ans = max(ans , tmp);
                vis[a[i]] = 1;
            }
        }
        printf("%d
" , ans);
    }
 
    return 0;
}