题解：AT_cpsco2019_s4_c Make a Team

_qumingnan_ · 2025-02-19 17:31:15 · 题解

题目跳楼机

正文开始

阅读理解

有 N 个数，从中选 3 个，要求最大数与最小数相差不超过 D，求有几种挑选方案？

思路：

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

#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)，过不了。

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

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

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

#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} 得到中间的选择方案数即可。

正确代码

#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;
}