双数组双指针解法
查看原帖
双数组双指针解法
1720859
zhaoyouyou123楼主2025/7/28 11:32

看了双指针的解法,感觉使用两个数组更好理解一些。特别是有相同被减数的情况下,可以使用组合方法解决,也挺明了。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[200001];
ll b[200001];
int main(){
	int n,c;
	
    cin >> n >>c ;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i]-c;
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	ll p_a=1;
	ll p_b=1;
	ll sum=0;
	while(p_a<=n&&p_b<=n)
	{

		if(a[p_a]==b[p_b]){
			int cnt_a=1;
			int cnt_b=1;
			while(a[p_a+cnt_a]==a[p_a]) cnt_a++;
			while(b[p_b+cnt_b]==b[p_b]) cnt_b++;
			sum+=cnt_a*cnt_b;
			p_a+=(cnt_a);
			p_b+=(cnt_b);
		}else if(a[p_a]<b[p_b]){
			p_a++;
		}else{
			p_b++;
		}
	}
	cout << sum;
    return 0;
}

2025/7/28 11:32
加载中...