题面：

　　小明已经厌倦了做菜，做菜对他来说太简单了。这天，他决定要挑战一下自己。 他已经选择了 N 根意大利面，准备做一道菜。他还需要选出一根意大利面，使得这根意大利面可以和已有的 N 根面中的某两根构成一个三角形。选出的意大利面的长度必须在 [L, R] 的范围内。 请你求出小明选择的方案数。

输入：

　　第一行给出N，L，R。 第二行给出N个数len1，len2，...，lenN，表示N个意大利面的长度。

　　2<=N<=1e6 1<=L，R<=1e18，1<=leni<=1e18

输出：

　　输出方案数。

样例：

Input:
5 1 4
1 2 3 4 5
Output:
3

这题卡了我很久。毕竟我之前没做过这一类的题目。

题意还是较为简单，不过就是从[L,R]的范围内能选出多少条条边与给出数组中的数凑成三角形。
看到数据规模自然是不能暴力的，毕竟O(n2)加上1e6的规模必然会炸。

首先毕竟题目是要凑三角形，我们必然就能想到三角形的性质：
1.任意两边之和大于第三边
2.任意两边之差小于第三边

我们假设我们在[L,R]内取了x长度的边，之后又从给出的长度数组A中取了Ai与Aj长度的边。
易得到以下的式子：
·x + Ai > Aj  ——> x > Aj - Ai
·x + Aj > Ai  ——> x > Ai - Aj
·Ai + Aj > x  ——> x < Ai + Aj
关于为什么是这三条式子，其实你就算写出了其他的也能化成这三条，我只是为了方便就拿了这样的式子。

所以我们就能很自然地想出，[L,R]与[max(Ai-Aj, Aj-Ai)+1, Ai+Aj-1]交集即为选取Ai与Aj的x的方案数。
上面的交集的意思就是既要在[L,R]范围内又要能与Ai和Aj组成三角形的范围。

但是关于怎么选取Ai与Aj确仍然是个问题。毕竟暴力的话还是O((R-L+1)*n2)。
这里引入一个很重要的结论：

假设这里有三个数A1 < A2 < A3,我们定义R(i,j)代表的是Ai,Aj能形成的三角形的范围。
所以
　　R(1,2)=[A2-A1+1,A2+A1-1],
　　R(2,3)=[A3-A2+1,A3+A2-1]
　　R(1,3)=[A3-A1+1,A3+A1-1]。
R(2,3)是完全包含R（1,3）的。这个也是较为好证明的，毕竟两个更大更相近的数所形成的三角形的范围，必然是要比两个较小相距较远的数来的大的。
（具体可以自己举例证明）

有了这个结论后我们就可以先将A数组排序，之后通过n-1对R(j-1,j)的并集（1-n总共有n-1个j与j-1)，再与[L,R]的交集即可以求出所求的方案数。
不过千万要注意特殊的情况，不然会WA很多发。

以下为AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    long long n,l,r;
    scanf("%lld %lld %lld",&n,&l,&r);

    ll a[n];

    for(ll i=0;i<n;i++)
    scanf("%lld",&a[i]);
    sort(a,a+n);

    ll sum,diff,ans=0;
    if (l > r)
    {
        cout << ans << endl;
        return 0;
    }

    for(ll i=n-1;i>0;i--)
    {
        sum = a[i]+a[i-1]-1;
        diff = a[i]-a[i-1]+1;
        //这里直接求交集
        ll s = max(l,diff);
        ll d = min(sum,r);
        if (s <= d)
            ans += d-s+1;
        //把选用过的长度去掉
        r = min(r,diff-1);
    }

    printf("%lld\n",ans);

    return 0;
}

View Code