选值&二分&组合数

悠悠 2022-05-26 10:46 38阅读 0赞

题目链接：[点击打开链接][Link 1]

题目描述

##  ##

给定n个数，从中选出三个数，使得最大的那个减最小的那个的值小于等于d，问有多少种选法。

## 输入描述: ##

第一行两个整数n，d(1 <= n <= 100,000，1 <= d <= 1000,000,000)；
    第二行n个整数满足abs(ai) <= 1,000,000,000。数据保证a单调递增。

## 输出描述: ##

输出一个整数表示满足条件的选法。

## 输入 ##

4 3
    1 2 3 4

输出

4 
         
          
        
         
       
        
      
       
      
       
       
        
         
        示例2
       
        
       
        
        
         
         
          输入 
         
          
          
           4 2
    -3 -2 -1 0 
         
          
        
         
        
         
         
          输出 
         
          
          
           2 
         
          
        
         
       
        
      
       
      
       
       
        
         
        示例3
       
        
       
        
        
         
         
          输入 
         
          
          
           5 19
    1 10 20 30 50 
         
          
        
         
        
         
         
          输出 
         
          
          
           1

//二分+组合数
    #include<stdio.h>
    #include<iostream>
    using namespace std;
    const int maxn=1e5+5;
    typedef long long ll;
    
    int n,d;
    int a[maxn];
    int find(int x,int i)
    {
        int l=i,r=n-1;
        int val=l;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(x<a[mid])
            {
                //val=mid;
                r=mid-1;
            }
            else///x>=a[mid]
            {
                val=mid;
                l=mid+1;
            }
        }
        return val;
    }
    int main()
    {
        while(cin>>n>>d)
        {
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
            }
            ll sum=0,cnt=0;
            for(int i=0;i<n-2;i++)
            {
                int max1=a[i]+d;
                int j=find(max1,i);
    
                cnt=j-i; //printf("j==%d  i=%d cnt=%d\n",j,i,cnt);
                sum+=cnt*(cnt-1)/2;
            }
            cout<<sum<<endl;
        }
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/84/F