题解：AT_abc417_c Distance Indicators

观察式子：

j - i = A_i + A_j

，移项可得：

i + A_i = j - A_j

，发现此时等式左边只与

i

有关，右边只与

j

有关。

考虑枚举

i

，每次将答案加上满足

i + A_i = j - A_j

的

j

的数量。

那么我们就需要先开一个 map，记为 cnt，在输入的时候对于每一个元素，进行 cnt[i - a[i]]++ 的操作。然后在枚举到每一个

i

的时候，进行 ans += cnt[i + a[i]] 统计答案。

题目说了

i < j

，我们这样统计会不会统计进

i = j

的情况？其实不会，题目保证了

A_i \not = 0

，因此不会有

i + A_i = i - A_i

的情况。

CPP

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
int n, a[N];
map <int, int> cnt;

int main(){
	
	ios :: sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i], cnt[i - a[i]]++;
	ll ans = 0;
	for(int i = 1; i <= n; i++)
		ans += cnt[i + a[i]];
	cout << ans;
	
	return 0;
}

题解：AT_abc417_c Distance Indicators

文章操作

相关推荐

评论

题解：AT_abc417_c Distance Indicators