小C的数组（array）

题目描述：

题目描述

小 C 终于成为一名萌新 OIer，最近他在学习数组。

小 C 要练习数组。一次，小 C 得到了一个长度为 n 的数组 a。

现在，对于每一个下标 i，小 C 想找出比 i 小. 且距离 i 最近的下标 j，使得满足 a[i] != a[j]，如果不存在，则 j = 0。记下标 i 对应的答案f[i] = j，小 C 为了确保自己的程序正确，想让你来检查 f 数组。

可你不能告诉他整个答案，你只需要告诉他 f 数组所有元素的和即可。
输入格式

从文件 array.in 中读取数据。

共两行，第一行一个正整数 n，表示数组长度；

第二行 n 个正整数，第 i 个表示 ai。
输出格式

输出到文件 array.out 中。

仅一行一个数，表示 f 数组所有元素的和。
输入输出样列
输入样例1：

6
1 1 2 3 2 1

输出样例1：

14

输入样例2：

12
3 3 3 3 2 2 2 2 4 4 1 1

输出样例2：

52

说明

【样例 1 解释】

f[i]依次为 (0, 0, 2, 3, 4, 5)，总和为 14。

【样例 2 解释】

f[i]依次为 (0, 0, 0, 0, 4, 4, 4, 4, 8, 8, 10, 10)，总和为 52。

【数据范围】

对于 40% 的数据：n ≤ 1000，1 ≤ a[i] ≤ 10，且保证数据随机；

对于 70% 的数据：n ≤ 10^6，1 ≤ a[i] ≤ 10，且保证数据随机；

对于 90% 的数据：n ≤ 10^6，1 ≤ a[i] ≤ 10；

对于 100% 的数据：n ≤ 10^6，1 ≤ a[i] ≤ 1000。

随机数据的生成方式如下：对于每一个 a[i]，等概率地从 1 到 10 中产生。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

思路1：暴力枚举，对于a[i]从a[1]枚举到a[i - 1]进行检查。
思路2：
像像a[i]与a[i - 1]的关系：如果a[i] != a[i - 1]那么f[i]就是i - 1，否则f[i]就是f[i - 1]

代码：

#include <bits/stdc++.h>

using namespace std ;

const int N = 1000010 ;
int n , res ;
int x[N] , f[N] ;

int main ()
{


	cin >> n ;
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] ;
		if (x[i] != x[i - 1]) f[i] = i - 1 ;
		else f[i] = f[i - 1] ;
	}
	for (int i = 1; i <= n; i++) res = res + f[i] ;
	cout << res << endl ;


	return 0 ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26