TESSOKU_BOOK A13. Close Pairs

Difficulty:None

問題

長さ$ Nの数列$ Aが与えられる。異なる整数のペアを選ぶ方法であって、差が$ K以上であるような選び方は何通りか。

解法

尺取り法の練習問題。

最後に同じ整数を選んでしまっているパターン数の$ Nを引くとよい。

実装

code:python

n,k = map(int,input().split())

a = list(map(int,input().split()))

r = 0

ans = 0

for l in range(n):

while r<n and ar-al<=k:

r+=1

ans += r-l

print(ans-n)

code:cpp

bool solve(){

LL(n,k);

vector<ll>a(n);cin >> a;

ll ans{},r{};

rep(l,n){

while(r<n and ar-al<=k)r++;

ans+=r-l;

}

O(ans-n);

return false;

}