选牛（二分查找）

淡淡的烟草味﹌ 2022-01-07 15:23 175阅读 0赞

### \#227. 选牛[   ][Link 1] ###

### 题目描述 ###

在一条坐标轴上，有n头奶牛，第i头奶牛的位置是Xi。FJ现在要选出三头奶牛去比赛，不妨假设选择了奶牛a，b，c。那么必须要满足：

1：Xa＜Xb＜Xc。

2：Xb-Xa≤Xc - Xb≤2×（Xb-Xa）。

你的任务是计算，FJ总共有多少种不同的选择？

### 输入输出格式 ###

#### 输入格式： ####

第一行，一个整数N。（3≤N≤1000）。

接下来有N行，第i行是整数Xi。

#### 输出格式： ####

一行，一个整数。

### 输入输出样例 ###

**输入样例：**

5
    3
    1
    10
    7
    4

**输出样例：**

### 说明 ###

**样例说明：**

可以有4种不同的选择，每种选择对应的3头奶牛的坐标是：

\{1，3，7\}

\{1，4，7\}

\{4，7，10\}

\{1，4，10\}

日常分析来了！！

\----------------------------------------------------

需要：

1.二分查找

2.枚举

首先看条件：

1：Xa＜Xb＜Xc。

2：Xb-Xa≤Xc - Xb≤2×（Xb-Xa）

那么我们就可以枚举Xa牛和Xb牛，再二分Xc牛

先不看第一个条件，那么我们就可以将第二个条件分解成:

1 Xb-Xa≤Xc-Xb 2 Xc-Xb≤2×(Xb-Xa)两条式子

先二分符合2.1条件的有多少牛，再二分符合2.2条件的有多少牛

再将2.2的结果减去2.1的结果就可以得出方案数了。

注：主要满足2.2而不是2.1，所以用2.2的结果减去2.1的结果

\----------------------------------------------------

努力理解，加油！！！！

#include<iostream>
    #include<fstream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int a[1000000];
    int n;
    int num,num1,t;
    int main()
    {
         scanf("%d",&n);
         for(int i=1;i<=n;i++)
         {
             scanf("%d",&a[i]);
         }
         sort(a+1,a+1+n);
         for(int i=1;i<=n;i++)
         {
             for(int j=1+i;j<=n;j++)
             {
                  int left=0,right=n+1;
                  while(left+1<right)
                {
                   int mid=(left+right)/2;
                    if(a[j]-a[i]>a[mid]-a[j])
                    {
                        left=mid;
                    }
                    else
                    {
                        right=mid;
                    }
                }
                num=left;
                left=0,right=n+1;
                while(left+1<right)
                {
                    int mid=(left+right)/2;
                    if(a[mid]-a[j]>2*(a[j]-a[i]))
                    {
                        right=mid;
                    }                    
                    else 
                    {
                        left=mid;
                    }
                }
                num1=left;
                t+=num1-num;
             }
         }
         cout<<t;
    
        return 0;
    }

转载于:https://www.cnblogs.com/wenzile/p/10723115.html

[Link 1]: http://119.23.110.242/contest/138/problem/227