题目链接
题意:
给定一个1-N的排列A1, A2, ... AN，每次操作小Hi可以选择一个数，把它放到数组的最左边。
请计算小Hi最少进行几次操作就能使得新数组是递增排列的。
思路:
这种题做过很多次了,就是换了个问法,本质都一样.可这次还是想了好久。。
这个题的话因为要求最小的操作数,而且要是严格递增的,由于每次只能放在最左边,所以我们想到逆着来做,从后往前,
从最大的开始,一定存在某个数只需要移动一次就可以.而且最多一共移动n次,如果当前的数满足递增序列的末尾,那么就
不需要移动,就把移动的次数-1,其他数来移动不会影响他的顺序.
#include<bits/stdc++.h> #define Ri(a) scanf("%d", &a) #define Rl(a) scanf("%lld", &a) #define Rf(a) scanf("%lf", &a) #define Rs(a) scanf("%s", a) #define Pi(a) printf("%d\n", (a)) #define Pf(a) printf("%lf\n", (a)) #define Pl(a) printf("%lld\n", (a)) #define Ps(a) printf("%s\n", (a)) #define W(a) while(a--) #define CLR(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define inf 0x3f3f3f3f #define exp 0.00000001 #define pii pair<int, int> #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn=1e5+10; int a[maxn]; int n; int main() { Ri(n); for(int i=1;i<=n;i++) { Ri(a[i]); } int ans=n; for(int i=n;i>=1;i--) { if(a[i]==n) { n--; ans--; } } Pi(ans); return 0; }
Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
