正文开始

阅读理解

有

N

个数，从中选

3

个，要求最大数与最小数相差不超过

D

，求有几种挑选方案？

思路：

先考虑暴力，依次枚举三个数，代码如下：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d;
int a[100005];
int ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);//排序防止重复 
	for(int i=1;i<=n-2;i++)//暴力枚举 
		for(int j=i+1;j<n;j++)
			for(int k=j+1;k<=n;k++)
				if(a[k]-a[i]<=d)ans++;//最大的与最小的相差不足D 
	cout<<ans;
	return 0;
}

很显然是

O(N^3)

，过不了。

注意到代码中有这一串代码：

CPP

if(a[k]-a[i]<=d)ans++;

这说明第二个循环是没有大用的，可以直接算出来，于是优化得到下面这个代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d;
int a[100005];
int ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n-2;i++)
			for(int k=i+2;k<=n;k++)
				if(a[k]-a[i]<=d)ans+=k-i-1;
	cout<<ans;
	return 0;
}

尽管省去了一个循环，但时间复杂度还是

O(N^2)

，还是过不了。

不难发现，因为数具有单调性，所以，我们可以把第二层循环变成二分，寻找到满足要求的最大值，再利用

C^2_{r-i}

得到中间的选择方案数即可。

正确代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d;
int a[100005];
int ans;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n-2;i++){
		int l=i+1,r=n;
		while(l<=r){
			int mid=l+r>>1;
			if(a[mid]-a[i]<=d)l=mid+1;
			else r=mid-1;
		}
		l--;
		ans+=(l-i)*(l-i-1)/2;
	}
	cout<<ans;
	return 0;
}

题解：AT_cpsco2019_s4_c Make a Team

文章操作

正文开始

阅读理解

思路：

正确代码

相关推荐

评论

题解：AT_cpsco2019_s4_c Make a Team