题目描述
等差数列，指从第二项起，每一项与它的前一项的差等于同一个常数的一种数列，且这个常数叫做等差数列的公差。
例如：数列 就是一个公差为 的等差数列。
现给定一个长度为 的序列 ， ， ， ，请问该序列中，有多少个长度不小于 的子段满足等差数列？
输入格式
输入共两行：
第一行，一个正整数 ，表示给定序列长度
第二行， 个整数，分别表示序列的每一项 , ,...,
输出格式
输出一个整数，表示满足条件的子段个数。
数据范围
-
对于 的数据，
-
对于 的数据，
-
对于 的数据， ，
样例数据
输入:
10
-1 1 3 3 3 2 3 2 1 0
输出:
5
说明:
区间[1,3],[3,5],[7,10],[7,9],[8,10]均满足等差数列要求
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
long long a[N], len = 2;
long long ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
long long gongCha = a[2] - a[1];
for (int i = 3; i <= n; i++) {
if (a[i] - a[i - 1] == gongCha) {
len++;
} else {
if (len >= 3)
ans += (1 + len - 2) * (len - 2) / 2;
len = 2;
gongCha = a[i] - a[i - 1];
}
}
if (len >= 3)
ans += (1 + len - 2) * (len - 2) / 2;
cout << ans;
return 0;
}
共 2 条回复
不要在意这些细节
第三行1 5 9 13公差为4吧