选牛（二分查找）

佚名 6年前 (2019-04-17) 随笔 1186人围观抢沙发百度已收录

#227. 选牛

题目描述

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

1：Xa＜Xb＜Xc。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

输入输出格式

输入格式：

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

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

输出格式：

一行，一个整数。

输入输出样例

输入样例：

输出样例：

说明

样例说明：

可以有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;
}