第四题:T4夹心饼干
标签:思维、数学
题意:给定一个数列
a
1
,
a
2
,
a
3
.
.
.
,
a
n
a_1,a_2,a_3...,a_n
a1,a2,a3...,an,请求出在这个序列中,能挑出多少个三个数
a
i
,
a
j
,
a
k
a_i,a_j,a_k
ai,aj,ak,满足
i
<
j
<
k
i<j<k
i<j<k且
a
i
=
a
k
a_i=a_k
ai=ak且
a
i
≠
a
j
a_i \neq a_j
ai=aj。
(
1
≤
n
≤
300
,
000
,
0
≤
a
i
<
n
)
(1≤n≤300,000,0≤a_i<n)
(1≤n≤300,000,0≤ai<n)
题解:观察题目中给的样例:
1
2
1
2
1
1\ 2\ 1\ 2\ 1
1 2 1 2 1,第
1
1
1个位置的
1
1
1和第
3
3
3个位置的
1
1
1中间夹了一个
2
2
2;
第
1
1
1个位置的
1
1
1和第
5
5
5个位置的
1
1
1之间夹了两个
2
2
2;第
2
2
2个位置的
2
2
2和第
4
4
4个位置的
2
2
2之间夹了
1
1
1个
1
1
1;第
3
3
3个位置的
1
1
1和第
5
5
5个位置的
1
1
1中间夹了一个
2
2
2。
可以把所有相同的数的下标按顺序放到对应的
v
e
c
t
o
r
vector
vector里面。
那么任意一对相同的数之间能够夹的数的个数就等于,两个数的下标之差 - 两个数中间包含的相同数个数。
比如
1
1
1维护的
v
e
c
t
o
r
vector
vector:
1
3
5
1\ 3 \ 5
1 3 5。
原序列的下标
1
1
1和下标
5
5
5之间能夹的数的个数就等于
5
−
1
−
(
3
−
1
)
=
2
5-1-(3-1)=2
5−1−(3−1)=2。
注意题目中的细节,
a
i
a_i
ai可能等于
0
0
0。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10;
ll n, x, mx = 0, ans = 0;
vector<ll> a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x;
mx = max(mx, x);
a[x].push_back(i);
}
for (int k = 0; k <= mx; k++) {
for (int i = 0; i < a[k].size(); i++) {
for (int j = i + 1; j < a[k].size(); j++) {
// 两个相同的数下标距离差-两个中间包含的相同数个数
ans += (a[k][j] - a[k][i] - (j - i));
}
}
}
cout << ans << endl;
return 0;
}