CodeForces 251A 2점
Note that the order of the points inside the group of three chosen points doesn't matter.
Input
The first line contains two integers: n and d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). The next line contains n integers x1, x2, ..., xn, their absolute value doesn't exceed 109 — the x-coordinates of the points that Petya has got.
It is guaranteed that the coordinates of the points in the input strictly increase.
Output
Print a single integer — the number of groups of three points, where the distance between two farthest points doesn't exceed d.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.
Sample Input
Input
4 3
1 2 3 4
Output
4
Input
4 2
-3 -2 -1 0
Output
2
Input
5 19
1 10 20 30 50
Output
1
Hint
In the first sample any group of three points meets our conditions.
In the seconds sample only 2 groups of three points meet our conditions: {-3, -2, -1} and {-2, -1, 0}.
In the third sample only one group does: {1, 10, 20}.
제목: n개점, 거리 d, 집합 중 세 개마다 가장 멀고 먼 거리가 d를 초과하지 않는 집합을 찾아낸다.
사고방식: 출발점을 선정한 다음에 2분으로 상계를 찾아 개수를 구하고 복잡도는 nlogn이다
코드:
#include <stdio.h>
#include <string.h>
long long n, d;
long long i, j;
long long num[100005];
long long ans = 0;
long long find(long long start, long long i, long long j) {
long long mid;
while (i < j) {
mid = (i + j) / 2;
if (num[mid] - num[start] <= d) {
i = mid + 1;
}
else {
j = mid;
}
}
mid = (i + j) / 2;
if (num[mid] - num[start] > d)
mid --;
return mid;
}
int main() {
scanf("%lld%lld", &n, &d);
for (i = 0; i < n; i ++)
scanf("%lld", &num[i]);
for (i = 0; i < n - 2 ; i ++) {
int j = find(i, i + 2, n - 1);
if (j - i < 2) continue;
ans += (j - i) * (j - i - 1) / 2;
}
printf("%lld
", ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.