Đếm số cặp có hiệu nhỏ hơn k trong mảng

#1

image
image877×515 121 KB

hiện tại e đang bị quá time : https://www.ideone.com/jJqbbE
các a sửa giúp e hoặc cho e ý tưởng cách làm khác

1 Like
#2

Sắp xếp lại trước rồi dùng hai trỏ, một trỏ vào ngay đầu và một trỏ vào số tiếp theo trong khoảng k bước. Dùng sentinel để giảm sự phức tạp của điều kiện.

7 Likes
#4

cái này sử dụng lower_bound() để tìm đúng ko a?

#7

a ơi,bài e thiếu gì mà bị gắn cờ thế a

#8

Dư chứ không thiếu.
Dư từ: “code mẫu”. Nó bằng với “làm giùm” đấy. Mà ban đầu, bạn cần ý tưởng.

4 Likes
#9

Nên tìm tuyến tính trước để thấy rõ các trường hợp có thể xảy ra.

5 Likes
#10

e có nói code mẫu à anh ơi

#11 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,x;
		cin>>n>>x;
		int a[n+5],check[10000+5] = {0};
		long long dem=0;
		for(int i=0;i<n;i++){
			cin>>a[i];
			check[a[i]]=1;
		}
		stable_sort(a,a+n);
		for(int i=0;i<n-1;i++){
			int temp = a[i] + x;
			int c;
			
			int temp2 = lower_bound(a,a+n,temp)-a;
			c = temp2 - i-1;
			if(c>=1){
				dem+=c;
			}
		}
		cout<<dem<<endl;
		
	}
}

ban co the tham khao

#12

Mảng toàn là số nên ko cần stable đâu :smiley:

3 Likes
#13 
#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n,k;
	long long dem=0;
	cin>>n>>k;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n-1;i++){
		int id=upper_bound(a,a+n,a[i]+k-1)-a;
		dem=dem+1LL*(id-i-1);
	}
	cout<<dem<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--)
	solve();
}
#14

mn cho e hỏi sao e code bài này chạy đúng nhưng nộp bài lại bị wa ạ , code ở dưới ạ , em cảm ơn::

#include<bits/stdc++.h>
using namespace std;
int last_poss(int a[],int l,int r,int x){
	int res=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]<x){
			res=m;
			l=m+1;
			}
		else{
			r=m-1;
		}
	}
	return res;
	}
int first_poss(int a[],int l,int r,int x){
	int res=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(a[m]>x){
			res=m;
			r=m-1;
			}
		else{
			l=m+1;
		}
	}
	return res;
	}		
int main(){
	int t;
	cin >> t;
	while(t--){
	int n,k;
	cin >> n >> k;
	int a[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		}
	int ans=0;	
	sort(a,a+n);
	for(int i=0;i<n;i++){
		int l=i+1;
		int r=n-1;
		int res=last_poss(a,l,r,k+a[i]);
		if(res != -1){
			ans+=res-i;
			}
		}
		cout<<ans<<endl;
		}
		return 0;
		}
#15

dg rồi
dùng lower_bound dc đó

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?