201509-1. 数列分段.md

【CCF CSP-20150901】数列分段

题意概述

给定一个整数数列，数列中连续相同的最长整数序列算成一段，问数列中共有多少段？

输入输出格式

输入的第一行包含一个整数 n，表示数列中整数的个数。第二行包含 n 个整数，表示给定的数列，相邻的整数之间用一个空格分隔。

输出一个整数，表示给定的数列有多个段。

数据规模

$1\le n \le 1000$，数列中的整数都是不超过 1000 的正整数。

算法设计

很简单的一道题，用好 find_if 函数可以让代码更简洁。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ans = 0;
    cin >> ni;
    vector<gg> ai(ni);
    for (gg& i : ai) {
        cin >> i;
    }
    for (gg i = 0, j; i < ai.size(); i = j) {
        //找到ai[i]右侧第一个不等于ai[i]的值
        j = find_if(ai.begin() + i, ai.end(),
                    [&ai, i](gg a) { return a != ai[i]; }) - ai.begin();
        ++ans;
    }
    cout << ans;
    return 0;
}