第三个超时,求救,排序用的快排
  • 板块P1102 A-B 数对
  • 楼主telankesi
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/12/31 20:00
  • 上次更新2023/10/24 05:59:43
查看原帖
第三个超时,求救,排序用的快排
866969
telankesi楼主2022/12/31 20:00
 #include <stdio.h>
int a[200010];
void fun(int l,int r) {
	if (l >= r)return;
	else {
		int t = a[(l+r)/2];
		a[(l + r) / 2] = a[l];
		a[l] = t;
		int x = l;
		int y = r;
		while (x != y) {
			while (a[y] >= t && x < y) 
				y--;
			while (a[x] <= t && x < y)x++;
			if (x < y) {
				int m = a[x];
				a[x] = a[y];
				a[y] = m;
			}
		}
		
		a[l] = a[x];
		a[x] = t;
		fun(l, x - 1);
		fun(x + 1, r);
	}
}
int main() {
	int n,c;
	scanf("%d %d", &n,&c);//a-b=c
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	fun(1,n);
	int num = 0;
	int l = 1, r = 1;
	for (int i = 1; i <= n; i++) {
		long long t = a[i]+c;
		
		while (  r <= n&& a[r] <= t) { r++; }
		while (l<=n&& a[l] < t) { l++; }
		
		
			num += r - l;
		
		
	}
	printf("%d", num);
	return 0;
}
2022/12/31 20:00
加载中...