题目描述见:P1102
qwq大致思路是将A-B=C变成A=B+C,其中C是确定的,并且题目说重复的也算ww(如果需要不重复的话开两个数组,给其中一个数组去重就行了qwq)那么在数组有序的情况下只需要枚举数组中的每一个数,然后用二分来找存在几个B+C,因为数组有序所以B+C一定是连续的,故寻找第一个出现的位置和最后一个出现的位置,相减+1获得B+C数量qwq....但还是有一些小细节ww
主要可能是我二分现在暂时只能用y总的模版吧,还不能灵活运用,而且也没法理解其他dalao写的二分QAQ好菜啊www...接下来先看代码吧ww
#include <iostream>
#include <algorithm>
typedef long long LL; //注意数据规模,一定要开longlong
using namespace std;
LL a[200010];
int n,c;
int Rfind(int x)//找a[i]-C的右端点数的函数
{
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)>>1;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
return l;
}
int Lfind(int x) { //找a[i]-C的左端点数的函数
int l = 1, r = n, mid;
while (l < r) {
mid = (l + r) / 2;
if (a[mid] >= x)
r = mid;
else
l = mid + 1;
}
return l;
}
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a+1, a + n+1 );
LL ans = 0;
for(int i=1;i<=n;i++){
int k=a[i]+c;
if(k>a[n]) continue; //特判,如果+c后大于最后一个数,find函数会返回n,最后+1导致WA
ans += Rfind(k)-Lfind(k)+1;
}
cout << ans;
return 0;
}