11273: 【原1273】上升数列

题目

题目描述

author: Chen Xutong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1273

Description

任何一个数列都可以划分成若干个严格上升的序列拼起来的形式，如{1, 4, 4, 2, 6, 3} 可分成 {1, 4},{4}, {2, 6}, {3}, 共4段。给定一个数列，问这个数列最少是由几个严格上升的数列拼接而成的。     

Sample Input

8
1 1 9 9 2 2 3 3

Sample Output

6
解释: {1, 1, 9, 9, 2, 2, 3, 3} = {1} + {1, 9} + {9} + {2} + {2, 3} + {3}

Limits

n <= 1e5

a_i <= 1e9

yyong119's solution

#include <cstdio>
#define MAX_N 200010
using namespace std;
int N, result;
int list[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
main(){
    N = read();
    for(register int i = 0; i < N; ++i) list[i] = read();
    for(register int i = 1; i < N; ++i)
        if (list[i] >= list[i - 1]) ++result;
    printf("%d\n", result);
    return 0;
}