笔试刷题-摩拜2018-08-05

题目描述：

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

思路如下：

Node{val, idx}
按照val先排序
排序后的node从第二个开始
若产生逆序把idx更新为当前最大模拟放到队尾，然后计数
总复杂度：
排序预处理O(nlogn)
计数处理O(n)

代码如下：

#include<stdio.h>
#include<iostream>
#include<algorithm>
 
#define MAX_N 51
 
using namespace std;
 
struct Node{
    int val=-1, idx=-1;
    Node(){}
    Node(int val, int idx){
        this->val=val;
        this->idx=idx;
    }
    Node(const Node &node){
        this->val=node.val;
        this->idx=node.idx;
    }
};
 
bool NodeCmpByVal(const Node &n1, const Node &n2){
    return n1.val<n2.val;
}
 
Node nodes[MAX_N];
 
int main()
{
    int N;
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        int val, idx=i;
        scanf("%d", &val);
        nodes[i]=Node(val, idx);
    }
    sort(nodes, nodes+N, NodeCmpByVal);
    int res=0, tailIdx=N;
    for(int i=1; i<N; i++){
        if(nodes[i].idx<nodes[i-1].idx){
            res++;
            nodes[i].idx=tailIdx;
            tailIdx++;
        }
    }
    printf("%d", res);
    return 0;
}