序列查询 CSP202112-1

 

 

 思路：

f(i)的范围从0到n，而且都是一段一段的，然后发现一个特性：每一段f（i）的区间范围是：

a[i]到a[i+1]-1.

于是，我们可以用这个区间长度乘这个区间的值，这个值正好是i，因为是小于x的最大数的下标嘛。

这样我们遍历每一个区间，把每个区间的算出来，再加起来就OK了。

AC代码：

#include 
using namespace std;
const int N = 210;
int n, m;
int a[N];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	a[n + 1] = m;
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res += i * (a[i + 1] - a[i]);
	}
	cout << res;
	return 0;
}