度度熊有一个N个数的数组,他想将数组从大到小排好序,但是萌萌的度度熊只会下面这个操作:
任取数组中的一个数然后将它放置在数组的最后一个位置.
问最少操作多少次可以使得数组从小到大有序?
输入描述:
首先输入一个正整数N,接下来的一行输入N个整数。(N <= 50, 每个数的绝对值小于等于1000)
输出描述:
输出一个整数表示最少的操作次数。
输入例子:
4
19 7 8 25
输出例子:
2
思路很简单,使用vcetor来装数组,使用map放value和index。
首先,对vector进行排序,这样我们会发现,vector中的值在map的索引号应该逐渐增大。
当发现vector中较大的值对应map中的索引号较小,应该把vector中较大的值对应的map中的索引号
以vector.size()为基数增大。
这里写代码片
#include "iostream"
#include "vector"
#include "map"
#include "algorithm"
using namespace std;
int main()
{
int N,value;
cin>>N;
vector<int> arr;
map<int,int> duMap;
for(int i=0;i<N;i++)
{
cin>>value;
arr.push_back(value);
duMap[value]=i;
}
sort(arr.begin(),arr.end());
int index=N,count=0;
for(int i=0;i<N-1;i++)
{
if(duMap[arr[i]]>duMap[arr[i+1]])
{
duMap[arr[i+1]]=index++;
count++;
}
}
cout<<count;
return 0;
}