92 WA3求助
  • 板块P1102 A-B 数对
  • 楼主yashi258
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/29 09:29
  • 上次更新2024/1/29 11:00:28
查看原帖
92 WA3求助
935299
yashi258楼主2024/1/29 09:29
#include<iostream>

using namespace std;

void xier_sort(int arr[],int n)
{
	for (int d = n / 2; d >= 1; d=d/2)
	{
		for (int i = d+1; i <= n; i++)
		{
			arr[0] = arr[i];
			int j = i - d;
			while (j >= 1)
			{
				if (arr[j] > arr[0])
				{
					arr[j + d] = arr[j];
					j -= d;
				}
				else
					break;
			}
			arr[j + d] = arr[0];
		}
	}
}


int erfen_search(int arr[], int n, int target)
{
	
	long long count = 0;
	long long num[2000000] = { 0 };
	for (int j = 1; j <= n; j++)
	{
		int end = n;
		if ((arr[end] - arr[j]) < target)
		{
			j +=1;
		}
		else
		{
			if (arr[j] == arr[j - 1]&&target!=0&&j>=2)
			{
				num[j] = num[j - 1];
				count += num[j];
			}
			else
			{
				int first = j;
				while (first <= end)
				{
					int mid = (first + end) / 2;
					if ((arr[mid] - arr[j]) > target)
					{
						end = mid - 1;
					}
					else if ((arr[mid] - arr[j]) < target)
					{
						first = mid + 1;
					}
					else
					{
						num[j]+= 1;
						count += 1;
						for (int x = mid - 1; x >= j; x--)
						{
							if (arr[x] == arr[mid])
							{
								count++;
								num[j]++;
							}
							else
								break;
						}
						for (int x = mid + 1; x <= end; x++)
						{
							if (arr[x] == arr[mid])
							{
								count++;
								num[j] ++ ;
							}
							else
								break;
						}
						break;

					}
				}
			}
		}
	}
	return count;

}
int main()
{
	int n, target;
	int arr[20000010];

	cin >> n>> target;

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	xier_sort(arr,n);
	int a=erfen_search(arr, n, target);
	cout << a;
}
2024/1/29 09:29
加载中...