汕头市队赛 SRM 07 B 好玩的麻将

B 好玩的麻将 SRM 07

背景&&描述

   天才麻将少女KPM立志要在日麻界闯出一番名堂。
   KPM上周又打了n场麻将，又控了分使得自己的排名是1..n的一个排列。
   但她这次想让妹子相信，闭关之后她的水平稳定上升。
   KPM出卖灵魂之后，膜法使答应用自己操控时间的能力帮助她。
   膜法使每次操作可以把某场比赛提到最前面或者最后面。
   膜法使急着去分享人生经验，问你最少需要多少次操作可以使KPM的排名单调递增。

输入格式

第一行一个整数n，第二行n个整数，表示n场比赛的排名。

输出格式

一个整数，表示最少需要操作多少次。

样例输入

4

1 4 3 2

样例输出

数据范围与约定

对于100%的数据: $1leq nleq 10^5$

这道题经大佬们转换之后就变成了求最长的连续递增的子序列x 然后n-x就是答案了 ....

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int M=1e5+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
int n,pos[M],k,mx,sum=1;
int main()
{
    n=read();
    for(int i=1;i<=n;i++) k=read(),pos[k]=i;
    for(int i=2;i<=n;i++){
        if(pos[i]>pos[i-1]) sum++;
        else{
            mx=max(mx,sum);
            sum=1;
        }
    }
    mx=max(mx,sum);
    printf("%d
",n-mx);
    return 0;
}

View Code