C/C++,#2、#3TLE,求助大佬们
查看原帖
C/C++,#2、#3TLE,求助大佬们
642429
Laplace_Song楼主2023/3/24 20:31
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

void QS(int A[], int start, int end)
{
	if (start == end) return;
	int stand = A[start], i = start + 1, j = end - 1;
	while (1)
	{
		while (A[i] < stand && i < end) i++;
		while (A[j] >= stand && j > start) j--;
		if (i < j) swap(A[i], A[j]);
		else break;
	}
	swap(A[start], A[j]);
	QS(A, start, j);
	QS(A, j + 1, end);
}

int BinSearch(int number[], int key, int head, int rear)
{
	if (rear < head) return -1;
	int middle = head + (rear - head) / 2;
	if (key == number[middle]) return middle;
	if (key < number[middle]) return BinSearch(number, key, head, middle - 1);
	else return BinSearch(number, key, middle + 1, rear);
}

int main()
{
	int N, sum = 0;
	int C;
	scanf("%d%d", &N, &C);
	int* A = new int[N];
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);
	QS(A, 0, N);

	int* number = new int[N];
	int* count = new int[N];
	for (int i = 0; i < N; i++) count[i] = 0;
	int len = 0;
	int j = 0;
	while (j < N)
	{
		number[len] = A[j];
		for (; j < N; j++)
		{
			if (number[len] == A[j]) count[len]++;
			else break;
		}
		len++;
	}

	int k = 0;
	for (int i = 0; i < len; i++)
	{
		int front, behind;
		front = number[i]; behind = C + front;
		int mark = BinSearch(number, behind, i + 1, len - 1);
		if (mark != -1) sum = sum + count[i] * count[mark];
	}
	printf("%d", sum);
	return 0;
}
2023/3/24 20:31
加载中...