笔试刷题-百度2018-06-04

题目描述：

/**
度度熊有一个N个数的数组，他想将数组从小到大 排好序，
但是萌萌的度度熊只会下面这个操作：
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序？
输入描述:
首先输入一个正整数N，接下来的一行输入N个整数。
(N <= 50, 每个数的绝对值小于等于1000)

输出描述:
输出一个整数表示最少的操作次数。

输入例子1:
4
19 7 8 25

输出例子1:
2
*/

思路如下：

直接bf模拟

采用模拟的方式计数即可，没一个节点有一个idx val, 其实就是一旦发现 nodes[i].val 大于 nodes[i+1].val且 nodes[i].idx>nodes[i+1].idx 产生一个逆序，那么其操作只能把nodes[i].val对应的noddes[i].idx变为当前最大的idx+1

不断检查，并计数，知道不产生逆序即可

此处采用非结构体实现，用map简单实现

代码如下：

//这里假设所有的数字都是不相同的
//哈希key为数字的绝对值
#include<stdio.h>
#include<iostream>
#include<algorithm>

#define OFFSET 1000
#define MAX_N 105
#define MAX_UNIVERSE 2005

using namespace std;

int data[MAX_N];
int idxMap[MAX_UNIVERSE];

int main(){
    int N, idxPtr, cnt = 0;
    scanf("%d", &N);
    idxPtr = N;
    for(int i=0; i<N; i++){
        scanf("%d", data+i);
        data[i] += OFFSET;
        idxMap[data[i]] = i;
    }
    sort(data, data+N);
    for(int i=0; i<N-1; i++){
        if(idxMap[data[i]]>idxMap[data[i+1]]){
            idxMap[data[i+1]] = idxPtr;
            idxPtr++;
            cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}