汕头市队赛 SRM 06 B 起伏的排名

B 起伏的排名 SRM 06

背景&&描述

天才麻将少女KPM立志要在日麻界闯出一番名堂。
在上个星期她打了n场麻将，每场麻将都有n名玩家。KPM自然记得自己的n次排名。
KPM有高超的控分技巧，所以她的n次排名是1..n的一个排列。
为了让妹子相信自己最近比赛状态起伏不定不宜外出，KPM想要从n场比赛里选出一个子序列，使得第一场排名>第二场的，第二场排名<第三场的，第三场的>第四场的....
总之除了选出来的第一场，选出来的其他场的排名要么<选出来的相邻两场的排名要么>选出来的相邻两场的排名。并且第一场排名要>第二场的。
你不需要输出具体的场次，只需要输出符合要求的子序列可能的最大长度就好了。。

只选一场也是满足条件的。

输入格式

第一行一个整数n。

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

输出格式

一个整数，表示最大的长度。

样例输入

6
5 2 1 6 4 3

样例输出

数据范围与约定

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

这道题就是求一个大小大小大小的序列其中大小是相对于相邻两个数而言

我们可以分情况考虑答案

1. 前一个数是 ‘大’ （定义为last）那么我们下一个数一定要比他小这时我们考虑当前数（定义为now）

如果now<last 很明显符合那么答案++

如果last>=now 那么前面小于last的以及后面能<last的同样能符合now 那么我们完全可以用now代替last

2 前一个数是 ‘下' 同1

所以这个问题就转换成了求拐点数拐点数+1就是答案了 2333

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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,ans=1,last,now,f;
int main()
{
    n=read(); 
    last=read(); f=1;
    for(int i=1;i<n;i++){
        now=read();
        if(now<last&&f==1) f=-1,ans++;
        if(now>last&&f==-1) f=1,ans++;
        last=now;
    }
    printf("%d
",ans);
    return 0;
}

View Code