问题描述
解题思路
????令
N
=
A
n
+
1
N=A_{n+1}
N=An+1?，则有：
0
=
A
0
<
A
1
<
?
?
?
<
A
i
<
?
?
?
<
A
n
<
A
n
+
1
=
N
0=A_0<A_1<···<A_i<···<A_n<A_{n+1}=N
0=A0?<A1?<???<Ai?<???<An?<An+1?=N
????对于
A
i
≤
x
<
A
i
+
1
,
0
≤
i
≤
n
A_i\le x<A_{i+1},0\le i\le n
Ai?≤x<Ai+1?,0≤i≤n，有
f
(
x
)
=
i
f(x)=i
f(x)=i。则：
s
u
m
(
A
)
=
∑
i
=
0
n
(
(
A
i
+
1
?
A
i
)
?
i
)
sum(A)=\sum_{i=0}^{n}((A_{i+1}-A_i)*i)
sum(A)=i=0∑n?((Ai+1??Ai?)?i)
????以题目中的样例一(
n
=
3
n=3
n=3)为例：
s
u
m
(
A
)
=
∑
i
=
0
3
(
(
A
i
+
1
?
A
i
)
?
i
)
=
(
A
1
?
A
0
)
?
0
+
(
A
2
?
A
1
)
?
2
+
(
A
3
?
A
2
)
?
2
+
(
A
4
?
A
3
)
?
3
=
(
2
?
0
)
?
0
+
(
5
?
2
)
?
1
+
(
8
?
5
)
?
2
+
(
10
?
8
)
?
3
=
15
\begin{aligned} sum(A)&=\sum_{i=0}^{3}((A_{i+1}-A_i)*i)\\ &=(A_1-A_0)*0+(A_2-A_1)*2+(A_3-A_2)*2+(A_4-A_3)*3\\ &=(2-0)*0+(5-2)*1+(8-5)*2+(10-8)*3\\ &=15 \end{aligned}
sum(A)?=i=0∑3?((Ai+1??Ai?)?i)=(A1??A0?)?0+(A2??A1?)?2+(A3??A2?)?2+(A4??A3?)?3=(2?0)?0+(5?2)?1+(8?5)?2+(10?8)?3=15?
AC代码
#include <vector>
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, N;
cin >> n >> N;
vector<int> A;
A.emplace_back(0);
for (int i = 1; i <= n; ++i)
{
int A_i;
cin >> A_i;
A.emplace_back(A_i);
}
A.emplace_back(N);
int sum = 0;
for (int i = 0; i <= n; ++i)
{
sum += (A[i + 1] - A[i]) * i;
}
cout << sum << endl;
return 0;
}