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

题目描述：

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


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

输入例子1:
4
19 7 8 25

输出例子1:
2

4
4 3 2 1
*/

思路如下：

第一次把第二小放到最后
第二次把第三小放到最后
以此类推即可
先把Node按照val排序,若val相同按原来输入数据的idx排序即可
Node{val, idx}用idx模拟移动到最后即可
按val排序后就可顺序遍历模拟依次把逆序的第二小或第三小等移动到队尾

代码如下：

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

#define MAX_N 55

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 operator < (const Node&node) const
    {
        return this->val<node.val;
    }
};

Node nodes[MAX_N];

int main()
{
    int N, idxPtr, cnt=0;
    scanf("%d", &N);
    idxPtr=N;
    for(int i=0; i<N; i++)
    {
        int idx=i, val;
        scanf("%d", &val);
        nodes[i]=Node(val, idx);
    }
    sort(nodes, nodes+N);
    for(int i=1; i<N; i++)
    {
        if(nodes[i-1].idx>nodes[i].idx)
        {
            nodes[i].idx=idxPtr;
            idxPtr++;
            cnt++;
        }
    }
//判断最大的一个是否需要放到队尾
    if(nodes[N-1].idx==N-1 && idxPtr>N)
    {
        nodes[N-1].idx=idxPtr;
        idxPtr++;
        cnt++;
    }
    printf("%d", cnt);
    return 0;
}